Crown graph

Crown graph
Crown graphs with six, eight, and ten vertices.

In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj 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, 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.



The 6-vertex crown graph forms a cycle, and the 8-vertex crown graph is isomorphic to the graph of a cube.


A biclique cover of the ten-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 {ui, vi} as one of the color classes.[1] Crown graphs are symmetric and distance-transitive. Archdeacon et al. (2004) 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.[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

\sigma(n)=\min \left\{\,k \mid n \le \binom{k}{\lfloor k/2 \rfloor} \,\right\},

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 \square Kn, or equivalently the 2 × n rook's graph.


In 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[4] 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, ... (sequence A094047 in OEIS)

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 [5]. 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č & Poroč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.


  1. ^ Chaudhary & Vishwanathan (1997).
  2. ^ Erdős & Simonovits (1980).
  3. ^ DeCaen, Gregory & Pullman (1981).
  4. ^ 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.
  5. ^ Kubale (2004)


  • Agarwal, Pankaj K.; Alon, Noga; Aronov, Boris; Suri, Subhash (1994), "Can visibility graphs be represented compactly?", Discrete and Computational Geometry 12 (1): 347–365, doi:10.1007/BF02574385 .
  • Archdeacon, D.; Debowsky, M.; Dinitz, J.; Gavlas, H. (2004), "Cycle systems in the complete bipartite graph minus a one-factor", Discrete Mathematics 284 (1–3): 37–43, doi:10.1016/j.disc.2003.11.021 .
  • Chaudhary, Amitabh; Vishwanathan, Sundar (1997), "Approximation algorithms for the achromatic number", SODA '97: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 558–563 .
  • de Caen, Dominique; Gregory, David A.; Pullman, Norman J. (1981), "The Boolean rank of zero-one matrices", in Cadogan, Charles C., Proc. 3rd Caribbean Conference on Combinatorics and Computing, Department of Mathematics, University of the West Indies, pp. 169–173 .
  • Erdős, Paul; Simonovits, Miklós (1980), "On the chromatic number of geometric graphs", Ars Combinatoria 9: 229–246 .
  • Fürer, Martin (1995), "Improved hardness results for approximating the chromatic number", Proc. 36th IEEE Symp. Foundations of Computer Science (FOCS '95), pp. 414–421, doi:10.1109/SFCS.1995.492572 .
  • Johnson, D. S. (1974), "Worst-case behavior of graph coloring algorithms", Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematicae, Winnipeg, pp. 513–527 
  • Kubale, M. (2004), Graph Colorings, American Mathematical Society, ISBN 0-8218-3458-4 
  • Matoušek, Jiří (1996), "On the distortion required for embedding finite metric spaces into normed spaces", Israel Journal of Mathematics 93 (1): 333–344, doi:10.1007/BF02761110 .
  • Miklavič, Štefko; Poročnik, Primož (2003), "Distance-regular circulants", European Journal of Combinatorics 24 (7): 777–784, doi:10.1016/S0195-6698(03)00117-3 .

External links

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Circulant graph — The Paley graph of order 13, an example of a circulant graph. Crown graphs …   Wikipedia

  • Complete bipartite graph — A complete bipartite graph with m = 5 and n = 3 Vertices n + m Edges mn …   Wikipedia

  • Armed Forces of the Crown — Streitkräfte des Vereinigten Königreichs Führung Oberbefehlshaber de jure …   Deutsch Wikipedia

  • Ménage problem — A table with ten place settings. According to the solution to the ménage problem, there are 3120 different ways in which five couples can choose seats at this table in such a way that men and women alternate and do not sit next to their partners …   Wikipedia

  • Order dimension — A partial order of dimension 4 (shown as a Hasse diagram) and four total orderings that form a realizer for this partial order. In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the… …   Wikipedia

  • Problème des ménages —  Ne doit pas être confondu avec Lemme des mariages. Une table à dix couverts. D après la solution au problème des ménages, il y a 3120 manières différentes, pour 5 couples, de s asseoir en alternant hommes et femmes et sans qu aucu …   Wikipédia en Français

  • Internal ballistics — Internal ballistics, a subfield of ballistics, is the study of a projectile s behavior from the time its propellant s igniter is initiated until it exits the gun barrel. The study of internal ballistics is important to designers and users of… …   Wikipedia

  • TAG Heuer — Infobox Company name = TAG Heuer SA type = Member of the LVMH group foundation = 1860 by Edouard Heuer location city = La Chaux de Fonds location country = Switzerland location = locations = key people = Jean Christophe Babin, President CEO Jack… …   Wikipedia

  • Business and Industry Review — ▪ 1999 Introduction Overview        Annual Average Rates of Growth of Manufacturing Output, 1980 97, Table Pattern of Output, 1994 97, Table Index Numbers of Production, Employment, and Productivity in Manufacturing Industries, Table (For Annual… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”