For a positive integer 
, the 
-crown
graph is the graph obtained from the complete
bipartite graph 
by deleting a perfect matching 
(Brouwer and Koolen 1999, van Dam and Haemers 2003). It is
denoted here by 
.
Equivalently, it is the graph with vertex
set
 |
(1)
|
and edge set
 |
(2)
|
It is also isomorphic to the rook complement graph 
(Brouwer et al. 1989, p. 222, Theorem 7.5.2, item (iii)), where 
denotes the graph
Cartesian product. Colbrook and Drysdale (2026) instead denote the same graph
by 
, with the two subscripts
giving the sizes of the two bipartition classes.
The analogous construction obtained by deleting a perfect matching from 
is the complete tripartite
graph minus perfect matching.
Note that the term "crown graph" has also been used to refer to a sunlet graph 
(e.g., Gallian 2018).
The 
-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).
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 (Proposition 9(ii) in van Dam and Haemers (2003)).
The line graph of the 
-crown graph is the arrangement
graph 
.
The 
-crown graph is isomorphic to the Haar
graph 
.
Other special cases are summarized in the following table.
The 
-crown graph 
has 
vertices and 
edges.
The numbers of directed Hamiltonian cycles for 
, 4, 5, ... are given by 2, 12, 312,
9600, 416880, ... (OEIS A094047), which has
the beautiful closed form
 |
(3)
|
(M. Alekseyev, pers. comm., Feb. 10, 2008).
Closed formulas for the numbers 
of 
-graph cycles of 
are given by 
for 
odd and
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
(E. Weisstein, Nov. 16, 2014).
The independence polynomial of the 
-crown graph is
 |
(7)
|
which satisfies the recurrence equation
 |
(8)
|
Colbrook and Drysdale (2026) proved that 
maximizes the representation
number among all bipartite graphs on 
vertices,
with
![R(K_(n,n)-M)={2 for 1<=n<=3; 3 for n=4; [n/2] for n>=5.](/images/equations/CrownGraph/NumberedEquation6.svg) |
(9)
|
where ![[x]](/images/equations/CrownGraph/Inline43.svg)
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.
