Articles

Wielgrafiek

Discrete Wiskunde > Grafentheorie > Eenvoudige Grafieken > Kegelgrafieken >
Discrete Wiskunde > Grafentheorie > Eenvoudige Grafieken > Sierlijke Grafieken >
Discrete Wiskunde > Grafentheorie > Eenvoudige Grafieken > Integrale Grafieken >

DOWNLOAD Mathematica NotebookWheelGraphs

Zoals in dit werk gedefinieerd, een wielgrafiek W_n van orde n, soms eenvoudigweg een n-wiel genoemd (Harary 1994, p. 46; Pemmaraju en Skiena 2003, p. 248; Tutte 2005, p. 78), is een grafiek die een cyclus van orde n-1 bevat en waarvoor elk grafiekvertex in de cyclus verbonden is met één ander grafiekvertex, bekend als de hub. De ribben van een wiel die de naaf omvatten worden spaken genoemd (Skiena 1990, p. 146). Het wiel W_n kan worden gedefinieerd als de grafiek join K_1+C_(n-1), waarbij K_1 de singleton-grafiek is en C_n de cyclus-grafiek, waardoor het een (n,1)-kegel-grafiek is.

Merk op dat er twee conventies zijn voor de indexering voor wiel-grafieken, waarbij sommige auteurs (bijv, Gallian 2007), nemen de conventie aan dat W_n de wielgrafiek op n+1 knopen aanduidt.

De tetrahedrale grafiek (d.w.z. K_4) isomorf met W_4, en W_5 isomorf met de volledige tripartiete grafiek K_(1,2,2). In het algemeen is de n-wielgrafiek het skelet van een (n-1)-piramide.

W_5 is een van de twee grafieken die verkregen worden door twee ribben te verwijderen uit de pentatopegrafiek K_5, de andere is de huis X-grafiek.

Wielgrafieken zijn sierlijk (Frucht 1979).

De wielgrafiek W_n heeft grafiekdimensie 2 voor n=7 (en is dus eenheidsafstand) en dimensie 3 anders (en is dus geen eenheidsafstand) (Erdős et al. 1965, Buckley and Harary 1988).

Elke wielgrafiek is een zelfduale grafiek.

Wielgrafieken kunnen in de Wolfram Language worden geconstrueerd met WheelGraph. Vooraf berekende eigenschappen van een aantal wielgrafieken zijn beschikbaar via GraphData.

WheelGraphCycles4WheelGraphCycles5

Het aantal grafiekcycli in de wielgrafiek W_n wordt gegeven door n^2-3n+3, of 7, 13, 21, 31, 43, 57, … (OEIS A002061) voor n=4, 5, ….

In een wielgrafiek heeft het knooppunt graad n-1, en hebben de andere knooppunten graad 3. Wielgrafieken zijn 3-connected. W_4=K_4, waarbij K_4 de volledige grafiek van orde vier is. Het chromatische getal van W_n is

 chi(W_n)={3 for n odd; 4 for n even.
(1)

De wielgrafiek W_n heeft chromatische polynoom

 pi(x)=x.
(2)