Properties
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 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.
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.
Read more about this topic: Crown Graph
Famous quotes containing the word properties:
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)