Crown graph

Crown graph
Crown graphs with six, eight, and ten vertices
Vertices	2 n
Edges	n (n - 1)
Radius	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}$
Diameter	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}$
Girth	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\6&n=3\\4&{\text{otherwise}}\end{array}}\right.}$
Chromatic number	${\displaystyle \left\{{\begin{array}{ll}1&n=1\\2&{\text{otherwise}}\end{array}}\right.}$
Properties	Distance-transitive
Notation	${\displaystyle S_{n}^{0}}$

In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices u_i and v_i and with an edge from u_i to v_j whenever i ≠ j. The crown graph can be viewed as a complete bipartite graph from which the edges of a perfect matching have been removed, as the bipartite double cover of a complete graph, as the tensor product K_n × K₂, or as a bipartite Kneser graph H_n,1 representing the 1-item and (n − 1)-item subsets of an n-item set, with an edge between two subsets whenever one is contained in the other.

The 6-vertex crown graph forms a cycle, and the 8-vertex crown graph is isomorphic to the graph of a cube. In the Schläfli double six, a configuration of 12 lines and 30 points in three-dimensional space, the twelve lines intersect each other in the pattern of a 12-vertex crown graph.

The number of edges in a crown graph is the pronic number n(n − 1). Its achromatic number is n: one can find a complete coloring by choosing each pair {u_i, v_i} as one of the color classes. Crown graphs are symmetric and distance-transitive. Archdeacon et al. (2004) describe partitions of the edges of a crown graph into equal-length cycles.