Articles

Hjulgraf

Diskret matematik > Grafteori > Enkla grafer > Konusgrafer >
Diskret matematik > Grafteori > Enkla grafer > Graciösa grafer >
Diskret matematik > Grafteori > Enkla grafer > Integralgrafer >

DOWNLOAD Mathematica NotebookWheelGraphs

Som definierat i detta arbete, en hjulgraf W_n av ordningen n, som ibland helt enkelt kallas ett n-hjul (Harary 1994, s. 46; Pemmaraju och Skiena 2003, s. 248; Tutte 2005, s. 78), är en graf som innehåller en cykel av ordningen n-1 och för vilken varje grafvertikal i cykeln är ansluten till en annan grafvertikal som kallas nav. De kanter i ett hjul som inkluderar navet kallas ekrar (Skiena 1990, s. 146). Hjulet W_n kan definieras som grafen join K_1+C_(n-1), där K_1 är singletongrafen och C_n är cykelgrafen, vilket gör det till en (n,1)-kongrafi.

Bemärk att det finns två konventioner för indexering av hjulgrafer, där vissa författare (t.ex, Gallian 2007), antar konventionen att W_n betecknar hjulgrafen på n+1 noder.

Den tetraedriska grafen (dvs. K_4) är isomorf till W_4, och W_5 är isomorf till den kompletta trepartsgrafen K_(1,2,2). I allmänhet är grafen n-hjulgrafen skelettet till en (n-1)-pyramid.

W_5 är en av de två grafer som erhålls genom att ta bort två kanter från pentatopgrafen K_5, den andra grafen är hus X-grafen.

Hjulgrafer är graciösa (Frucht 1979).

Hjulgrafen W_n har grafen dimension 2 för n=7 (och är därmed enhetsdistans) och dimension 3 i övrigt (och är därmed inte enhetsdistans) (Erdős et al. 1965, Buckley och Harary 1988).

Alla hjulgrafer är självduella grafer.

Hjulgrafer kan konstrueras i Wolframspråket med WheelGraph. Förberäknade egenskaper för ett antal hjulgrafer finns tillgängliga via GraphData.

WheelGraphCycles4WheelGraphCycles5

Antalet grafcykler i hjulgrafen W_n ges av n^2-3n+3, eller 7, 13, 21, 31, 43, 57, … (OEIS A002061) för n=4, 5, ….

I en hjulgraf har navet grad n-1, och andra noder har grad 3. Hjulgrafer är 3-anslutna. W_4=K_4, där K_4 är den kompletta grafen av ordning fyra. Det kromatiska talet för W_n är

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

Den hjulgrafen W_n har kromatiskt polynom

 pi(x)=x.
(2)