(0,2)-Graph

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).

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 and folded cube graphs. 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 , 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.