Hjulgraf - Wheel graph

Hjulgraf
Flera exempel på hjuldiagram
Hörn	n
Kanter	2 ( n - 1)
Diameter	2 om n > 4 1 om n = 4
Omkrets	3
Kromatiskt nummer	4 om n är jämnt 3 om n är udda
Spektrum	${\ displaystyle \ {2 \ cos (2k \ pi / (n-1)) ^ {1};}$ ${\ displaystyle k = 1, \ ldots, n-2 \}}$${\ displaystyle \ cup \ {1 \ pm {\ sqrt {n}} \}}$
Egenskaper	Hamiltonian självdubbel planar
Notation	W n
Tabell över grafer och parametrar

I den matematiska disciplinen för grafteori är ett hjuldiagram ett diagram som bildas genom att ansluta ett enda universellt toppunkt till alla hörn i en cykel . Ett hjuldiagram med n hörn kan också definieras som 1- skelettet för en ( n -1) -gonal pyramid . Vissa författare skriver W _{n för} att beteckna ett hjuldiagram med n hörn (n ≥ 4); andra författare använder istället W _{n för} att beteckna ett hjuldiagram med n +1 hörn (n ≥ 3), som bildas genom att ansluta ett enda toppunkt till alla hörn i en cykel med längd n . I resten av denna artikel använder vi den tidigare notationen.

Byggmästarkonstruktion

Med en vertexuppsättning av {1, 2, 3,…, v}, kan kantuppsättningen för hjuldiagrammet representeras i set-build-notationen med {{1, 2}, {1, 3},…, {1 , v}, {2, 3}, {3, 4},…, {v - 1, v}, {v, 2}}.

Egenskaper

Hjuldiagram är plana grafer och har som sådan en unik plan inbäddning. Mer specifikt är varje hjulgraf ett Halin-diagram . De är självdubbla: den plana dubbla för varje hjulgraf är en isomorf graf. Varje maximal planär graf, annat än K ₄ = W ₄ , innehåller som en subgraf antingen W ₅ eller W ₆ .

Det finns alltid en Hamilton-cykel i hjulgrafen och det finns cykler i W _n (sekvens A002061 i OEIS ). ${\ displaystyle n ^ {2} -3n + 3}$

Hjuldiagrammet W _{4: s} 7 cykler .

För udda värden på n är W _n ett perfekt diagram med kromatiskt nummer 3: hörnpunkterna i cykeln kan ges två färger och mittpunkten får en tredje färg. För ännu n , W _n har kromatisk nummer 4, och (när n ≥ 6) är inte perfekt. W ₇ är det enda hjuldiagrammet som är ett enhetsavståndsdiagram i det euklidiska planet.

Den kromatiska polynomet av hjulet grafen W _n är:

${\ displaystyle P_ {W_ {n}} (x) = x ((x-2) ^ {(n-1)} - (- 1) ^ {n} (x-2)).}$

I matroidteorin är två särskilt viktiga specialklasser av matroider hjulmatroiderna och virvelmatroiderna , båda härledda från hjuldiagram. Den k -wheel matroid är den grafiska matroid av ett hjul W _{k + 1} , under det att k -whirl matroid härleds från k -wheel genom att betrakta den yttre cykeln av hjulet, liksom alla dess spänner träd , att vara självständig.

Hjulet W ₆ gav ett motexempel till en antagande av Paul Erds om Ramsey-teorin : han hade antagit att hela grafen har det minsta Ramsey-antalet bland alla grafer med samma kromatiska tal, men Faudree och McKay (1993) visade att W ₆ har Ramsey nummer 17 medan den fullständiga grafen med samma kromatiska antal, K ₄ , har Ramsey nummer 18. det vill säga, för varje 17-vertex graf G , antingen G eller dess komplement innehåller W ₆ som en subgraf, medan varken 17-vertex Paley grafen eller dess komplement innehåller en kopia av K ₄ .

Referenser