 TOPICS  # (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.

Hexacode Graph, Regular Graph

## Explore with Wolfram|Alpha More things to try:

## References

Brouwer, A. E. http://www.win.tue.nl/~aeb/graphs/Dodecahedral-02.html.Brouwer, A. E. http://www.win.tue.nl/~aeb/graphs/recta/02graphs.html.Brouwer, A. E. "Classification of Small -Graphs." J. Combin. Th. Ser. A 113, 1636-1645, 2006.Brouwer, A. E. and Östergård, P. R. J. "Classification of the -Graphs of Valency 8." Preprint. http://www.win.tue.nl/%7Eaeb/graphs/recta/recta8b.dvi.Sloane, N. J. A. Sequences A202592 in "The On-Line Encyclopedia of Integer Sequences."

## Cite this as:

Weisstein, Eric W. "(0,2)-Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/02-Graph.html