Wheel graph

Wheel graph
Several examples of wheel graphs
Vertices	$n \geq 4$
Edges	$2(n - 1)$
Diameter	2 if $n > 4$ 1 if $n = 4$
Girth	3
Chromatic number	4 if $n$ is even 3 if $n$ is odd
Spectrum	$\{2\cos(2k\pi /(n-1))^{1};$ $k=1,\ldots ,n-2\}$ $\cup \{1\pm {\sqrt {n}}\}$
Properties	Hamiltonian Self-dual Planar
Notation	$W n$
Table of graphs and parameters

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 $n$ vertices can also be defined as the 1-skeleton of an ( $n - 1$ )-gonal pyramid.

Some authors^[1] write $W n$ to denote a wheel graph with $n$ vertices ( $n \geq 4$ ); other authors^[2] instead use $W n$ to denote a wheel graph with $n + 1$ vertices ( $n \geq 3$ ), which is formed by connecting a single vertex to all vertices of a cycle of length $n$ . 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}}^[3] 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₄ = W₄, contains as a subgraph either W₅ or W₆.

There is always a Hamiltonian cycle in the wheel graph and there are $n^{2}-3n+3$ cycles in W_n (sequence A002061 in the OEIS).

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₇ is the only wheel graph that is a unit distance graph in the Euclidean plane.^[4]

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₆ 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₆ has Ramsey number 17 while the complete graph with the same chromatic number, K₄, has Ramsey number 18.^[5] That is, for every 17-vertex graph G, either G or its complement contains W₆ as a subgraph, while neither the 17-vertex Paley graph nor its complement contains a copy of K₄.

References

^ Weisstein, Eric W. "Wheel Graph". MathWorld.
^ Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications (7th ed.). McGraw-Hill. p. 655. ISBN 978-0073383095.
^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 56. ISBN 978-0-486-67870-2. Retrieved 8 August 2012.
^ Buckley, Fred; Harary, Frank (1988), "On the euclidean dimension of a wheel", Graphs and Combinatorics, 4 (1): 23–30, doi:10.1007/BF01864150, S2CID 44596093.
^ Faudree, Ralph J.; McKay, Brendan D. (1993), "A conjecture of Erdős and the Ramsey number r(W₆)", J. Combinatorial Math. and Combinatorial Comput., 13: 23–31.

Read other articles:

FANUC

FANUC (/ˈfænʊk/; sering bergaya Fanuc) adalah sebuah kelompok perusahaan, terutama FANUC Corporation (ファナック株式会社 Fanakku Kabushikigaisha?) Dari Jepang, Fanuc America Corporation of Rochester Hills, Michigan, Amerika Serikat, dan FANUC Robotika Europe SA Luxembourg, yang menyediakan produk dan layanan otomatisasi seperti robotika dan komputer sistem kontrol numerik. FANUC adalah salah satu pembuat robot industri terbesar di dunia. Ini adalah bagian dari Furukawa Group. FAN...

Psikoanalisis

Bagian ini adalah seri artikel tentangPsikoanalisis Konsep Psikoseksual perkembangan Tahap perkembangan psikososial Erikson Alam bawah sadar Freud Prasadar Kesadaran Apparatus psikis Id, ego dan super-ego Libido Teori drive Transference Countertransference Mekanisme pertahanan ego Resistensi psikologi Proyeksi psikologi Penolakan Alam mimpi Tokoh penting Alfred Adler Michael Balint Wilfred Bion Josef Breuer Nancy Chodorow Max Eitingon Erik Erikson Ronald Fairbairn Paul Federn Otto Fenichel S�...

San Carlos de la Barra Fortress

You can help expand this article with text translated from the corresponding article in Spanish. (September 2015) Click [show] for important translation instructions. View a machine-translated version of the Spanish article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wi...

Первородный грех

Об экономическом термине см. Первородный грех (экономика). ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Ран�...

وزارة الإعلام (فلسطين)

لمعانٍ أخرى، طالع وزارة الإعلام (توضيح). وزارة الإعلام الفلسطينية وزارة الإعلام (فلسطين) تفاصيل الوكالة الحكومية البلد دولة فلسطين تأسست عام 1994 المركز رام الله31°53′34″N 35°12′01″E / 31.892733°N 35.200218°E / 31.892733; 35.200218 الإدارة منصب المدير وزير الإعلام ...

Leonard Cohen

Pour les articles homonymes, voir Cohen. Leonard CohenLeonard Cohen en 2008.BiographieNaissance 21 septembre 1934MontréalDécès 7 novembre 2016 (à 82 ans)Los Angeles (Californie, États-Unis)Sépulture Mont RoyalNom de naissance Leonard Norman CohenNationalité CanadienneDomiciles Montréal, WestmountFormation Université McGill (baccalauréat universitaire) (1951-1955)Pripstein's Camp Mishmar (en)Roslyn Elementary School (en)Camp B'nai Brith (en)Université ColumbiaÉcole secondaire...

Ираклеониты

Ираклеониты — ученики гностика Ираклеона (II век). Упоминаются как особая секта Епифанием и Августином; при крещении и миропомазании они соблюдали обряд помазания елеем и при этом произносили воззвания на арамейском языке, которые должны были освободить душу от власт�...

Eppo Doeve

Eppo Doeve, 1951 Joseph Ferdinand Doeve (2 Juli 1907 – 11 Juni 1981), lebih dikenal sebagai Eppo Doeve, adalah seorang pelukis dan kartunis terkenal berkebangsaan Belanda. Ia lahir di Bandung, Indonesia dan pindah ke Belanda pada 1927. Ia diberi gelar Ksatria dengan Order of Orange Nassau tahun 1973. Kartun-kartun karyanya banyak dipublikasikan di Elseviers Weekblad dan Elseviers Magazine. Pengawasan otoritas Umum Integrated Authority File (Jerman) ISNI 1 VIAF 1 WorldCat Perpu...

Франц (герцог Саксен-Кобург-Заальфельдский)

Франц Саксен-Кобург-Заальфельдскийнем. Franz von Sachsen-Coburg-Saalfeld герцог Саксен-Кобург-Заальфельдский 8 сентября 1800 — 9 декабря 1806 Предшественник Эрнст Фридрих Саксен-Кобург-Заальфельдский Преемник Эрнст I Саксен-Кобург-Заальфельдский Рождение 15 июля 1750(1750-07-15)Кобург, Сакс...

Oh No It Isn't!

1997 novel by Paul Cornell The topic of this article may not meet Wikipedia's notability guideline for books. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted.Find sources: Oh No It Isn't! – news · newspapers · books · schola...

土库曼斯坦总统

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府（Oguzkhan Presidential Palace）機關所在地阿什哈巴德任命者直接选举任期7年，可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日土库曼斯坦土库曼斯坦政府与政治国家政府土库曼斯坦宪法国旗国徽国歌立法機關（英语：National Council of Turkmenistan） ...

Historic Crew Stadium

Soccer Stadium in Columbus, Ohio Crew Stadium redirects here. For the new stadium opened in 2021, see Lower.com Field. Historic Crew StadiumAerial view of the stadium, 2018Former namesColumbus Crew Stadium (1999–2015)Mapfre Stadium (2015–2020)Address1 Black and Gold BoulevardLocationColumbus, OhioCoordinates40°0′34″N 82°59′28″W / 40.00944°N 82.99111°W / 40.00944; -82.99111OperatorColumbus CrewCapacity22,555 (1999–2008)20,145 (2008–2015)19,968 (2015�...

Anaho Island National Wildlife Refuge

National Wildlife Refuge in Nevada Anaho Island National Wildlife RefugeIUCN category IV (habitat/species management area)Map of the United StatesLocationWashoe County, Nevada, United StatesNearest cityReno, NevadaCoordinates39°57′15″N 119°30′30″W / 39.95417°N 119.50833°W / 39.95417; -119.50833Area247 acres (100 ha)Established1913Governing bodyU.S. Fish and Wildlife ServiceWebsiteAnaho Island National Wildlife Refuge The Anaho Island National...

Congregation Beth Israel (Austin, Texas)

Synagogue in Texas, United States It has been suggested that Austin synagogue arson be merged into this article. (Discuss) Proposed since March 2024. For similarly named synagogues, see Beth Israel. This article may rely excessively on sources too closely associated with the subject, potentially preventing the article from being verifiable and neutral. Please help improve it by replacing them with more appropriate citations to reliable, independent, third-party sources. (December 2023) (Learn...

Political impact of Hurricane Sandy

In late October 2012, the post-tropical cyclone once known as Hurricane Sandy made landfall in New Jersey. By the time it made landfall, it had merged with other storm systems. Though no longer a hurricane, the combined storm caused over $50 billion in damages and cost over 100 lives in the United States. The storm and its aftermath had several direct and indirect effects on the American political environment leading up to the 2012 United States General Election, in which Mitt Romney challeng...

Director of Public Prosecutions (Australia)

Australian federal prosecutions service Commonwealth Director of Public ProsecutionsAgency overviewFormed8 March 1984 (1984-03-08)Employees413[1]Minister responsibleMark Dreyfus, Attorney-General of AustraliaAgency executiveRaelene Sharp KC, Director of Public ProsecutionsParent departmentAttorney General's DepartmentWebsitecdpp.gov.au The Office of the Commonwealth Director of Public Prosecutions or, informally, the Commonwealth Director of Public Prosecutions (CDPP) i...

1900 United Kingdom general election

1900 United Kingdom general election ← 1895 26 September – 24 October 1900 (1900-09-26 – 1900-10-24) 1906 → ← outgoing memberselected members →All 670 seats in the House of Commons336 seats needed for a majorityTurnout75.1% First party Second party Leader Marquess of Salisbury Henry Campbell-Bannerman Party Conservative and Liberal Unionist Liberal Leader since April 1881 December 1898 Leader's&#...

Masjed Soleyman County

County in Khuzestan province, Iran For the city, see Masjed Soleyman. County in Khuzestan, IranMasjed Soleyman County Persian: شهرستان مسجد سلیمانCountyShahid Abbaspour DamLocation of Masjed Soleyman County in Khuzestan province (center right, pink)Location of Khuzestan province in IranCoordinates: 32°01′N 49°21′E / 32.017°N 49.350°E / 32.017; 49.350[1]Country IranProvinceKhuzestanCapitalMasjed SoleymanDist...

Jane Cunningham

American politician Jane CunninghamMember of the Missouri Senatefrom the 7th districtIn office2008–2012Preceded byJohn William LoudonSucceeded byJason Holsman Personal detailsBorn (1946-09-04) September 4, 1946 (age 77)Columbia, South CarolinaPolitical partyRepublicanSpouseGaryResidenceChesterfield, MissouriAlma materFlorida State UniversityProfessionMarketing Jane Cunningham (September 4, 1946) is an American politician from the state of Missouri. A Republican, Cunningham served as a ...

Azerbaïdjan

Pour les articles homonymes, voir Azerbaïdjan (homonymie). République d'Azerbaïdjan(az) Azərbaycan Respublikası Drapeau de l'Azerbaïdjan Emblème de l'Azerbaïdjan Hymne Azərbaycan Respublikasının Dövlət Himni (« Marche azerbaïdjanaise ») Fête nationale 28 mai · Événement commémoré Proclamation d'indépendance de la République démocratique d'Azerbaïdjan (1918) République d'Azerbaïdjan Administration Forme de l'État République présidentielle Pr�...