10
$\begingroup$

I was browsing the library and I found Bela Bollobás book "Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Probabilistic Combinatorics" and, on its cover, it has a graph that I don't quite recognize:

Graph from the cover

Is this graph any "interesting", as used for counterexamples (e.g., Petersen's Graph)? I could determine some of its characteristics (9 vertices, regular of valency 4, non-planar, diameter 2 etc.), but is it distinguished in any way for being featured in an important book?

  • 0
    BTW, all of the answers are superb and I don't know what to choose as "the" answer to this question...2012-12-21

4 Answers 4

1

It's the unit distance embedding of $K_3 \times K_3$, one of the few strongly regular graphs that has a unit distance embedding in $\mathbb{R}^2$. It is also known as $3 \times 3$ rook graph (though sometimes mistakenly as $3 \times 3$ grid graph). It also is a generalized quadrangle as pointed out above by A. Schulz.

8

It's isomorphic to the rook graph on a 3 by 3 grid:

Rook graph on a 3 by 3 grid

The Wikipedia page lists some nice properties of square rook graphs. For example, the graph is perfect, completely symmetric (i.e. looks the same from every vertex), it's the line graph of $K_{3,3}$, ...

8

This graph is known as the generalized quadrangle (2,1), it is also the line graph of the $K_{3,3}$, as well as the Paley-9 graph. See here for more information. I am not aware that it is used as a prominent counterexample.

4

It's also the Cartesian product of a 3-cycle with another 3-cycle.