A (0,2)-graph is a connected graph such that any two vertices have 0 or 2 common neighbors. (0,2)-graphs are regular, and the numbers of (0,2)-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 (0,2)-graphs are implemented in the Wolfram Language as GraphData[{"ZeroTwoBipartite", {d, k}}] and GraphData[{"ZeroTwoNonBipartite", {d, k}}].


Classes of graphs that are (0,2)-graphs include the hypercube and folded cube graphs. Particular named (0,2)-graphs are summarized in the following table, ordered by vertex degree, and some of which are illustrated above.

Brouwer considers the unique 20-vertex (0,2)-graph, denoted (20,16)-noncayley transitive graph above, which can be constructed by letting the vertices be the ordered pairs (i,j) of distinct elements from the 5-set (1,2,3,4,5), where (i,j) is adjacent to (i,k) whenever i, j, k are distinct and (i,j) is adjacent to (k,l) when i, j, k, l are distinct, so that (1,2,3,4,5)=(i,j,k,l,m) for some m, and the permutation that maps (1,2,3,4,5) to (i,j,k,l,m) 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.

See also

Hexacode Graph, Regular Graph

Explore with Wolfram|Alpha


Brouwer, A. E., A. E., A. E. "Classification of Small (0,2)-Graphs." J. Combin. Th. Ser. A 113, 1636-1645, 2006.Brouwer, A. E. and Östergård, P. R. J. "Classification of the (0,2)-Graphs of Valency 8." Preprint., 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.

Subject classifications