Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Crown graph
Summary
In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices {u_1, u_2, ..., u_n} and {v_1, v_2, ..., v_n} and with an edge from u_i to v_j 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 K_n × K_2, as the complement of the Cartesian direct product of K_n and K_2, or as a bipartite Kneser graph H_n,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 {u_i, v_i} as one of the color classes. Crown graphs are symmetric and distance-transitive. 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.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.