graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a branch of mathematics, a crown graph on vertices is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

with two sets of vertices and and with an edge from to whenever . The crown graph can be viewed as a

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...

from which the edges of a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactl ...

have been removed, as the

bipartite double cover In graph theory, the bipartite double cover of an undirected graph is a bipartite, covering graph of , with twice as many vertices as . It can be constructed as the tensor product of graphs, . It is also called the Kronecker double cover, cano ...

of a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

, as the

tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...

, as the complement of the Cartesian direct product of and , or as a bipartite Kneser graph representing the 1-item and -item subsets of an -item set, with an edge between two subsets whenever one is contained in the other.

Examples

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.

Properties

The number of edges in a crown graph is the

pronic number A pronic number is a number that is the product of two consecutive integers, that is, a number of the form n(n+1).. The study of these numbers dates back to Aristotle. They are also called oblong numbers, heteromecic numbers,. or rectangular number ...

. Its achromatic number is : one can find a

complete coloring In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on ''at least'' one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper ...

by choosing each pair as one of the color classes. Crown graphs are

symmetric Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...

and distance-transitive. describe partitions of the edges of a crown graph into equal-length cycles. The -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 dimensions. This example shows that a graph may require very different dimensions to be represented as a

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these gra ...

s 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 In the mathematical fields of graph theory and combinatorial optimization, the bipartite dimension or biclique cover number of a graph ''G'' = (''V'', ''E'') is the minimum number of bicliques (that is complete bipartite subgraphs), ...

, or the size of a minimum biclique cover) is :

\sigma(n)=\min \left\,

the inverse function of the central binomial coefficient. The

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...

of a -vertex crown graph is the Cartesian product of

s , or equivalently the

rook's graph In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on ...

Applications

In etiquette, a traditional rule for arranging guests at a dinner table is that men and women should alternate positions, and that no married couple should sit next to each other. The arrangements satisfying this rule, for a party consisting of ''n'' married couples, can be described as the

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

s of a crown graph. For instance, the arrangements of vertices shown in the figure can be interpreted as seating charts of this type in which each husband and wife are seated as far apart as possible. The problem of counting the number of possible seating arrangements, or almost equivalentlyIn the ménage problem, the starting position of the cycle is considered significant, so the number of Hamiltonian cycles and the solution to the ménage problem differ by a factor of 2''n''. the number of Hamiltonian cycles in a crown graph, is known in combinatorics as the

ménage problem In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of male-female couples at a round dining table so that men and women alternate and nobody sits ...

; for crown graphs with 6, 8, 10, ... vertices the number of (oriented) Hamiltonian cycles is :2, 12, 312, 9600, 416880, 23879520, 1749363840, ... Crown graphs can be used to show that

greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...

algorithms behave badly in the worst case: if the vertices of a crown graph are presented to the algorithm in the order ''u''₀, ''v''₀, ''u''₁, ''v''₁, etc., then a greedy coloring uses ''n'' colors, whereas the optimal number of colors is two. This construction is attributed to ; crown graphs are sometimes called Johnson’s graphs with notation ''J''_''n''. uses crown graphs as part of a construction showing hardness of approximation of coloring problems. uses distances in crown graphs as an example of a

metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...

that is difficult to embed into a

normed vector space In mathematics, a normed vector space or normed space is a vector space over the real or complex numbers, on which a norm is defined. A norm is the formalization and the generalization to real vector spaces of the intuitive notion of "length ...

. As show, crown graphs are one of a small number of different types of graphs that can occur as distance-regular circulant graphs. describe polygons that have crown graphs as their

visibility graph In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge rep ...

s; they use this example to show that representing visibility graphs as unions of complete bipartite graphs may not always be space-efficient. A crown graph with 2''n'' vertices, with its edges oriented from one side of the bipartition to the other, forms the standard example of a

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...

with

order dimension In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller di ...

''n''.

Notes

References

*. *. *. *. *. *. * * *. *.

External links

*{{mathworld, title=Crown Graph, urlname=CrownGraph Parametric families of graphs Regular graphs