Wheel graph

{{infobox graph | name = Wheel graph | image = Wheel graphs.svg | image_size = 220px | image_caption = Several examples of wheel graphs | girth = 3 | diameter = 2 if 1 if | vertices = | edges = | chromatic_number = 3 if is odd 4 if is even | chromatic_index = | spectrum = \{2\cos(2k\pi / (n - 1))^1; k = 1, \ldots, n - 2\} \cup\{1 \pm \sqrt{n}\} | properties = Hamiltonian Self-dual Planar | notation = }} In graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with vertices can also be defined as the 1-skeleton of an pyramid. Some authors write to denote a wheel graph with vertices ( ); other authors instead use to denote a wheel graph with vertices ( ), which is formed by connecting a single vertex to all vertices of a cycle of length . The former notation is used in the rest of this article and in the table on the right.

{{infobox graph | name = Wheel graph | image = Wheel graphs.svg | image_size = 220px | image_caption = Several examples of wheel graphs | girth = 3 | diameter = 2 if 1 if | vertices = | edges = | chromatic_number = 3 if is odd 4 if is even | chromatic_index = | spectrum = \{2\cos(2k\pi / (n - 1))^1; k = 1, \ldots, n - 2\} \cup\{1 \pm \sqrt{n}\} | properties = Hamiltonian Self-dual Planar | notation = }} In graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with vertices can also be defined as the 1-skeleton of an pyramid. Some authors write to denote a wheel graph with vertices ( ); other authors instead use to denote a wheel graph with vertices ( ), which is formed by connecting a single vertex to all vertices of a cycle of length . The former notation is used in the rest of this article and in the table on the right. ==Edge Set== {{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}} would be the edge set of a wheel graph with vertex set {1, 2, …, v} in which the vertex 1 is a universal vertex. ==Properties== Wheel graphs are planar graphs, and have a unique planar embedding. More specifically, every wheel graph is a Halin graph. They are self-dual: the planar dual of any wheel graph is an isomorphic graph. Every maximal planar graph, other than K 4 = W 4 , contains as a subgraph either W 5 or W 6 . There is always a Hamiltonian cycle in the wheel graph and there are n^2-3n+3 cycles in W n . For odd values of n, W n is a perfect graph with chromatic number 3: the vertices of the cycle can be given two colors, and the center vertex given a third color. For even n, W n has chromatic number 4, and (when n ≥ 6) is not perfect. W 7 is the only wheel graph that is a unit distance graph in the Euclidean plane. The chromatic polynomial of the wheel graph W n is : P_{W_n}(x) = x((x - 2)^{(n - 1)} - (-1)^n(x - 2)). In matroid theory, two particularly important special classes of matroids are the wheel matroids and the whirl matroids, both derived from wheel graphs. The k-wheel matroid is the graphic matroid of a wheel W k+1 , while the k-whirl matroid is derived from the k-wheel by considering the outer cycle of the wheel, as well as all of its spanning trees, to be independent. The wheel W 6 supplied a counterexample to a conjecture of Paul Erdős on Ramsey theory: he had conjectured that the complete graph has the smallest Ramsey number among all graphs with the same chromatic number, but Faudree and McKay (1993) showed W 6 has Ramsey number 17 while the complete graph with the same chromatic number, K 4 , has Ramsey number 18. That is, for every 17-vertex graph G, either G or its complement contains W 6 as a subgraph, while neither the 17-vertex Paley graph nor its complement contains a copy of K 4 . ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1366110914 under CC BY-SA 4.0; modifications have been made.