A -graph is a connected
graph such that any two distinct vertices have
0 or 2 common neighbors.
-graphs are regular, and
the numbers of
-graphs
with vertex degree 0, 1, 2, ... are given by 1,
1, 1, 2, 3, 8, 24, 96, 302, ... (OEIS A202592;
Brouwer).
A -graph with
vertices and vertex
degree
satisfies
To see this, fix a graph vertex and count the
two-step walks from
that do not return to
. Each other graph
vertex is the endpoint of either 0 or 2 such walks.
The graph Cartesian product of two -graphs is again a
-graph (Brouwer). If two distinct vertices
differ in only one coordinate, their common neighbors
are determined by that factor. If they differ in two coordinates, they have two common
neighbors exactly when the corresponding coordinates
are adjacent in both factors. In all other cases they have no common neighbors.
Consequently, a graph Cartesian product
of path graphs, with each
,
is a
-graph iff
every
is 1 or 2. In that case it is a hypercube graph
,
where
is the number of factors with
.
If some
, two vertices
that differ by two consecutive steps in that factor and agree in all other coordinates
have exactly one common neighbor.
The only complete multipartite graphs that are -graphs
are the singleton graph
,
the path graph
, the square
graph
, and the tetrahedral
graph
. Indeed, regularity
forces all nonempty parts to have the same size
.
With
parts, two vertices
in different parts have
common neighbors, while two distinct vertices
in the same part have
common neighbors. For
this gives
or
, and for
it gives
. The remaining connected
case is the singleton graph.
In particular, the only cubic -graphs are the tetrahedral
graph
and cubical graph
(Brouwer).
A subset of -graphs are implemented in the Wolfram
Language as GraphData[{"ZeroTwoBipartite",
{d, k}}] and GraphData[{"ZeroTwoNonbipartite",
{d, k}}].
Classes of graphs that are -graphs include the hypercube
graphs and the folded n-cube graphs
for
, 3, or
(Brouwer). The folded 4-cube is the complete
bipartite graph
, which is not a
-graph because two vertices
in the same part have four common neighbors. Particular
named
-graphs are summarized in the following
table, ordered by vertex degree, and some of which
are illustrated above.
| graphs | |
| 0 | singleton graph |
| 1 | 2-path graph |
| 2 | square graph |
| 3 | cubical graph |
| 4 | (2,4)-rook
graph, quartic vertex-transitive
graph Qt31, tesseract graph |
| 5 | 5-hypercube graph |
| 6 | hexacode
graph, 6-hypercube graph |
| 7 | 7-folded cube graph, 7-hypercube
graph |
| 8 | 8-folded
cube graph, 8-hypercube graph |
| 9 | (1,1)-Doob graph, (3,4)-Hamming
graph, 9-folded cube graph, 9-hypercube
graph |
| 10 | 10-folded
cube graph, 10-hypercube graph |
| 12 | (1,2)-Doob graph, (4,4)-Hamming graph, Leonard graph |
Brouwer considers the unique 20-vertex -graph whose local graphs
are all
. It can be constructed by letting the vertices
be the ordered pairs
of distinct elements from
the 5-set
, where
is adjacent to
whenever
,
,
are distinct and
is adjacent to
when
,
,
,
are distinct, so that
for some
,
and the permutation that maps
to
is an even permutation.
Equivalently, it can be constructed by letting the vertices
be the 20 vertices of the dodecahedron,
choosing a fixed set partition of the dodecahedron
into five tetrahedra, and letting two vertices
be adjacent whenever they either lie in a common tetrahedron,
or are joined by a graph edge of the dodecahedron.