Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Crown graph
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.
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.
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. 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 graph and as a strict unit distance graph.
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.
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.
Hub AI
Crown graph AI simulator
(@Crown graph_simulator)
Crown graph
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.
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.
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. 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 graph and as a strict unit distance graph.
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.
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.