| Crown graph | |||||||
| Chromatic Number: | \left\{\begin{array}{ll}1&n=1\ 2&otherwise\end{array}\right. \left\{\begin{array}{ll}infty&n\le2\ 3&otherwise\end{array}\right. \left\{\begin{array}{ll}infty&n\le2\ 3&otherwise\end{array}\right. \left\{\begin{array}{ll}infty&n\le2\ 6&n=3\ 4&otherwise\end{array}\right.
In graph theory, a branch of mathematics, a crown graph on vertices is an undirected graph with two sets of vertices and and with an edge from to whenever . 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, as the complement of the Cartesian direct product of and, or as a bipartite Kneser graph representing the 1-item and -item subsets of an -item set, with an edge between two subsets whenever one is contained in the other. ExamplesThe 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. PropertiesThe number of edges in a crown graph is the pronic number . Its achromatic number is : one can find a complete coloring by choosing each pair 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 -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 dimensions. This example shows that a graph may require very different dimensions to be represented as a unit distance graph 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 \sigma(n)=min\left\{k\midn\le\binom{k}{\lfloork/2\rfloor}\right\}, The complement graph of a -vertex crown graph is the Cartesian product of complete graphs, or equivalently the rook's graph. ApplicationsIn etiquette, a traditional rule for arranging guests at a dinner table is that men and women should alternate positions, and that no married couple should sit next to each other. The arrangements satisfying this rule, for a party consisting of n married couples, can be described as the Hamiltonian cycles of a crown graph. For instance, the arrangements of vertices shown in the figure can be interpreted as seating charts of this type in which each husband and wife are seated as far apart as possible. The problem of counting the number of possible seating arrangements, or almost equivalently[1] the number of Hamiltonian cycles in a crown graph, is known in combinatorics as the ménage problem; for crown graphs with 6, 8, 10, ... vertices the number of (oriented) Hamiltonian cycles is 2, 12, 312, 9600, 416880, 23879520, 1749363840, ... Crown graphs can be used to show that greedy coloring algorithms behave badly in the worst case: if the vertices of a crown graph are presented to the algorithm in the order u0, v0, u1, v1, etc., then a greedy coloring uses n colors, whereas the optimal number of colors is two. This construction is attributed to ; crown graphs are sometimes called Johnson’s graphs with notation Jn. uses crown graphs as part of a construction showing hardness of approximation of coloring problems. uses distances in crown graphs as an example of a metric space that is difficult to embed into a normed vector space. As show, crown graphs are one of a small number of different types of graphs that can occur as distance-regular circulant graphs. describe polygons that have crown graphs as their visibility graphs; they use this example to show that representing visibility graphs as unions of complete bipartite graphs may not always be space-efficient. A crown graph with 2n vertices, with its edges oriented from one side of the bipartition to the other, forms the standard example of a partially ordered set with order dimension n. References
External links | ||||||