A -graph is a connected graph such that any two 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).
Classes of graphs that are -graphs include the hypercube and folded cube graphs. Particular named -graphs are summarized in the following table, ordered by vertex degree, and some of which are illustrated above.
|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 , 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, denoted -noncayley transitive graph above, which 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 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 edge of the dodecahedron.