Crown graph
| Crown graph | |
|---|---|
Crown graphs with six, eight, and ten vertices | |
| Vertices | 2n |
| Edges | n(n − 1) |
| Radius | |
| Diameter | |
| Girth | |
| Chromatic number | |
| Properties | Distance-transitive |
| Notation | |
| Table of graphs and parameters | |
In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices {u1, u2, …, un} and {v1, v2, …, vn} 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, 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.