TOPICS
Search

Crown Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
CrownGraph

The n-crown graph, for a positive integer n, is the graph obtained from the complete bipartite graph K_(n,n) by deleting a perfect matching M (Brouwer and Koolen 1999, van Dam and Haemers 2003). It is denoted here by K_(n,n)-M. Equivalently, it is the graph with vertex set

{x_0,x_1,...,x_(n-1),y_0,y_1,...,y_(n-1)}
(1)

and edge set

{(x_i,y_j):0<=i,j<=n-1,i!=j}.
(2)

It is also isomorphic to the rook complement graph K_2 square K_n^_ (Brouwer et al. 1989, p. 222), where square denotes the graph Cartesian product. Colbrook and Drysdale (2026) instead denote the same graph by H_(n,n), with the two subscripts giving the sizes of the two bipartition classes.

The analogous construction obtained by deleting a perfect matching from K_(2n,2n,2n) is the complete tripartite graph minus perfect matching.

Note that the term "crown graph" has also been used to refer to a sunlet graph C_n circledot K_1 (Gallian 2025, p. 21).

The s-crowns used in the "crowning operation" (Koester 1990) are unrelated to the crown graphs defined here. Repeated application of that "crowning" operation to the Chiu graph generates an infinite family of quartic planar edge-critical graphs with fractional chromatic number 3 (Chiu et al. 2024).

For n>=3, the crown graphs are distance-transitive (Brouwer et al. 1989, p. 222), and therefore also distance-regular. They are also Taylor graphs, as well as determined by spectrum graphs (van Dam and Haemers 2003, p. 264).

For n>=2, the line graph of the n-crown graph is the arrangement graph A_(n,2).

For n>=2, the n-crown graph is isomorphic to the Haar graph H(3·2^(n-2)-1). Other special cases are summarized in the following table.

ngraph
1empty graph K^__2
2ladder rung graph 2P_2
3cycle graph C_6
4cubical graph Q_3

The n-crown graph K_(n,n)-M has 2n vertices and n(n-1) edges.

The nonorientable graph genus is

gamma^~(K_(n,n)-M)={0 for 1<=n<=4; 3 for n=5; ((n-1)(n-4))/2 for n>=6.
(3)

For n>=6, a nonorientable quadrangular graph embedding attains the lower bound obtained from the Euler characteristic (Singh and Sun 2023).

The numbers of directed Hamiltonian cycles for n=3, 4, 5, ... are given by 2, 12, 312, 9600, 416880, ... (OEIS A094047), which has the beautiful closed form

|HC(n)|=2(-1)^n(n-1)!+n!sum_(j=0)^(n-1)(-1)^j(n-j-1)!(2n-j-1; j)
(4)

(M. Alekseyev, pers. comm., Feb. 10, 2008).

Closed formulas for the numbers c_k of k-graph cycles of the n-crown graph are given by c_k=0 for k odd and

c_4=1/4(n-3)(n-2)(n-1)n
(5)
c_6=1/6(n-2)(n-1)n(n^3-9n^2+29n-32)
(6)
c_8=1/8(n-3)(n-2)(n-1)n(n^4-14n^3+79n^2-210n+218)
(7)

(E. Weisstein, Nov. 16, 2014).

The independence polynomial of the n-crown graph is

I_n(x)=2(x+1)^n+nx^2-1,
(8)

which satisfies the recurrence equation for n>=4

I_n(x)=(x+3)I_(n-1)(x)-(2x+3)I_(n-2)(x)+(x+1)I_(n-3)(x).
(9)

Colbrook and Drysdale (2026) proved that K_(n,n)-M maximizes the representation number among all bipartite graphs on 2n vertices, with

R(K_(n,n)-M)={2 for 1<=n<=3; 3 for n=4; [n/2] for n>=5.
(10)

where [x] is the ceiling function. The finite cases in the proof were certified by checked Boolean unsatisfiability certificates, and the theorem was also formalized in Lean.

Colbrook and Drysdale (2026) report that discussions with ChatGPT 5.5, 5.6, and 6 contributed to the ordering method, obstruction classification, and odd-part argument. They also used Codex for combinatorial counting, certificate construction and verification, and Lean formalization, and state that they reviewed and adopted all content.

See also

Cocktail Party Graph, Complete Bipartite Graph, Complete Tripartite Graph Minus Perfect Matching, Nonorientable Graph Genus, Rook Complement Graph, Taylor Graph

Portions of this entry contributed by Simone Severini

Explore with Wolfram|Alpha

References

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Brouwer, A. and Koolen, J. "The Distance-Regular Graphs of Valency Four." J. Algebraic Combin. 10, 5-24, 1999.Chiu, M.-K.; Felsner, S.; Scheucher, M.; Schröder, F.; Steiner, R.; and Vogtenhuber, B. "Coloring Circle Arrangements: New 4-Chromatic Planar Graphs." European J. Combin. 121, 103839, 2024. https://doi.org/10.1016/j.ejc.2023.103839.Colbrook, M. J. and Drysdale, C. "Crown Graphs Maximise the Representation Number of Bipartite Graphs." 24 Sep 2026. https://arxiv.org/abs/2609.35842.DistanceRegular.org. "Crown Graphs." https://www.math.mun.ca/distanceregular/indexes/crowngraphs.html.Gallian, J. A. "A Dynamic Survey of Graph Labeling." Elec. J. Combin., Dynamic Survey DS6, Oct. 30, 2025. https://doi.org/10.37236/27.House of Graphs. Crown Graphs. Empty Graph on 2 Vertices, 2K_2, C_6, The cube Q_3, Circulant C_10 (1,3), and others.Johnston, D.; Mark Kayll, P.; and Palmer, C. "Deranged Matchings: Proofs and Conjectures." 30 Oct 2022. https://arxiv.org/abs/2209.11319.Koester, G. "4-Critical 4-Valent Planar Graphs Constructed with Crowns." Math. Scand. 67, 15-22, 1990. https://doi.org/10.7146/math.scand.a-12316.Singh, W. and Sun, T. "Settling the Nonorientable Genus of the Nearly Complete Bipartite Graphs." Graphs Combin. 39, 96, 2023. https://doi.org/10.1007/s00373-023-02698-w.Sloane, N. J. A. Sequences A002378/M1581 and A094047 in "The On-Line Encyclopedia of Integer Sequences."van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 241-272, 2003. https://doi.org/10.1016/S0024-3795(03)00483-X.

Referenced on Wolfram|Alpha

Crown Graph

Cite this as:

Weisstein, Eric W., with contributions by Simone Severini. "Crown Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CrownGraph.html

Subject classifications