Crown graph

In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices {u_1, u_2, ..., u_n} and {v_1, v_2, ..., v_n} 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_2, as the complement of the Cartesian direct product of K_n and K_2, 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. describe partitions of the edges of a crown graph into equal-length cycles. The 2n-vertex crown graph may be embedded into four-dimensional Euclidean space in such a way that all of its edges have unit length. However, this embedding may also place some non-adjacent vertices a unit distance apart. An embedding in which edges are at unit distance and non-edges are not at unit distance requires at least n – 2 dimensions. This example shows that a graph may require very different dimensions to be represented as a unit distance graphs and as a strict unit distance graph. The minimum number of complete bipartite subgraphs needed to cover the edges of a crown graph (its bipartite dimension, or the size of a minimum biclique cover) is the inverse function of the central binomial coefficient.