Hjul graf

Hjuldiagram
Hjuldiagram
	Flera exempel på hjuldiagram
Vertices	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	;
Egenskaper	; ; Hamiltonian Self-dual Planar
Notation	W n
	Tabell över grafer och parametrar

Inom den matematiska disciplinen grafteori är en hjulgraf en graf som bildas genom att ansluta en enda universell vertex till alla hörn i en cykel . En hjulgraf med $n$ hörn kan också definieras som 1- skelettet av en ( $n - 1$ )-gonal pyramid . Vissa författare skriver $W n$ för att beteckna en hjulgraf med $n$ hörn ( $n \geq 4)$ ; andra författare använder istället $W n$ för att beteckna en hjulgraf med $n + 1$ hörn ( $n \geq 3$ ), som bildas genom att koppla en enda vertex till alla hörn av en cykel med längden $n$ . Resten av den här artikeln använder den tidigare notationen.

Set-byggare konstruktion

Givet en vertexuppsättning av {1, 2, 3, …, v}, kan kantuppsättningen av hjulgrafen representeras i set-builder-notation av {{1, 2}, {1, 3}, …, {1 , v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}.

Egenskaper

Hjuldiagram är plana grafer och har en unik plan inbäddning. Mer specifikt är varje hjulgraf en Halin-graf . De är självduala: den plana dualen i valfri hjulgraf är en isomorf graf . Varje maximal plan graf, förutom K ₄ = W ₄ , innehåller som en subgraf antingen W ₅ eller W ₆ .

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

Hjuldiagrammets 7 cykler W ₄ .

För udda värden på n är W _n en perfekt graf med kromatisk nummer 3: cykelns hörn kan ges två färger och mittpunkten ges en tredje färg . För jämn n har W _n kromatiskt nummer 4 och (när n ≥ 6) är inte perfekt . W ₇ är den enda hjulgrafen som är en enhetsdistansgraf i det euklidiska planet.

Det kromatiska polynomet i hjulgrafen W _n är:

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

Inom matroideorin är två särskilt viktiga specialklasser av matroider hjulmatroider och virvelmatroider , båda härledda från hjuldiagram. K - hjulsmatroiden är den grafiska matroiden för ett hjul W _k+1 , medan k -virvelmatroiden härleds från k -hjulet genom att betrakta hjulets yttre cykel, såväl som alla dess spännande träd , som oberoende.

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