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 , tetrahedral graph
4	(2,4)-rook graph, quartic vertex-transitive graph Qt31, tesseract graph
5	5-hypercube graph , Clebsch graph, icosahedral graph
6	hexacode graph, 6-hypercube graph , Kummer graph, (4,4)-rook graph, Shrikhande graph
7	7-folded cube graph, 7-hypercube graph , 24-Klein 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 , Gewirtz graph, Gewirtz bipartite double 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 an graph edge of the dodecahedron.