Crown graph
Crown graph | ||
---|---|---|
Edges n(n – 1) | | |
Radius | ||
Diameter | ||
Girth | ||
Chromatic number | ||
Properties | Distance-transitive | |
Notation | ||
Table of graphs and parameters |
In
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 Kn × K2, as the complement of the Cartesian direct product of Kn and K2, or as a bipartite Kneser graph Hn,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.
Examples
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.
Properties
The number of edges in a crown graph is the
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 graph and as a strict unit distance graph.[2]
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.[3]
The complement graph of a 2n-vertex crown graph is the Cartesian product of complete graphs K2 ▢ Kn, or equivalently the 2 × n rook's graph.
Applications
In
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 Johnson (1974); crown graphs are sometimes called Johnson’s graphs with notation Jn.[6] Fürer (1995) uses crown graphs as part of a construction showing hardness of approximation of coloring problems.
Matoušek (1996) uses distances in crown graphs as an example of a metric space that is difficult to embed into a normed vector space.
As Miklavič & Potočnik (2003) show, crown graphs are one of a small number of different types of graphs that can occur as distance-regular circulant graphs.
Agarwal et al. (1994) 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.
Notes
- ^ Chaudhary & Vishwanathan (2001).
- ^ Erdős & Simonovits (1980).
- ^ de Caen, Gregory & Pullman (1981).
- ISBN 9781118051375
- ^ In the ménage problem, the starting position of the cycle is considered significant, so the number of Hamiltonian cycles and the solution to the ménage problem differ by a factor of 2n.
- ^ Kubale (2004).
References
- MR 1298916.
- MR 2071894.
- Chaudhary, Amitabh; Vishwanathan, Sundar (2001), "Approximation algorithms for the achromatic number", Journal of Algorithms, 41 (2): 404–416, S2CID 9817850.
- MR 0657202.
- MR 0582295.
- Fürer, Martin (1995), "Improved hardness results for approximating the chromatic number", Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 414–421, S2CID 195870010.
- )
- Kubale, M. (2004), Graph Colorings, American Mathematical Society, MR 2074481
- S2CID 121050316.
- Miklavič, Štefko; Potočnik, Primož (2003), "Distance-regular circulants", MR 2009391.