Articles

Graficul roții

Matematică discretă > Teoria grafurilor > Grafuri simple > Grafuri conice >
Matematică discretă > Teoria grafurilor > Grafuri simple > Grafuri grafice grafice >
Matematică discretă > Teoria grafurilor > Grafuri simple > Grafuri integrale >

DOWNLOAD Mathematica NotebookWheelGraphs

Cum sunt definite în această lucrare, un graf roată W_n de ordinul n, uneori numit simplu un n-roată (Harary 1994, p. 46; Pemmaraju și Skiena 2003, p. 248; Tutte 2005, p. 78), este un graf care conține un ciclu de ordinul n-1 și pentru care fiecare vârf de graf din ciclu este conectat la un alt vârf de graf cunoscut sub numele de hub. Marginile unei roți care includ butucul se numesc spițe (Skiena 1990, p. 146). Roata W_n poate fi definită ca graful join K_1+C_(n-1), unde K_1 este graful singleton și C_n este graful ciclului, ceea ce o face un graf (n,1)conic.

Rețineți că există două convenții pentru indexarea grafurilor roată, unii autori (de ex, Gallian 2007), adoptând convenția că W_n denotă graful roată pe n+1 noduri.

Graful tetraedru (adică K_4) este izomorf cu W_4, iar W_5 este izomorf cu graful tripartit complet K_(1,2,2). În general, graful n-roată este scheletul unei piramide (n-1).

W_5 este unul dintre cele două grafuri obținute prin eliminarea a două muchii din graful pentatopului K_5, celălalt fiind graful casei X.

Grafurile roată sunt grațioase (Frucht 1979).

Graful roată W_n are dimensiunea grafică 2 pentru n=7 (și, prin urmare, are distanța unitară) și dimensiunea 3 în rest (și, prin urmare, nu are distanța unitară) (Erdős et al. 1965, Buckley și Harary 1988).

Care graf de roată este un graf auto-dual.

Grafele de roată pot fi construite în limbajul Wolfram folosind WheelGraph. Proprietățile precalculate ale unui număr de grafuri cu roți sunt disponibile prin GraphData.

WheelGraphCycles4WheelGraphCycles5

Numărul de cicluri de graf în graful cu roți W_n este dat de n^2-3n+3, sau 7, 13, 21, 31, 43, 57, … (OEIS A002061) pentru n=4, 5, ….

Într-un graf de roată, butucul are gradul n-1, iar celelalte noduri au gradul 3. Grafurile de roată au 3 conexiuni. W_4=K_4, unde K_4 este graful complet de ordinul 4. Numărul cromatic al lui W_n este

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

Ceea de graficul roții W_n are polinomul cromatic

 pi(x)=x.
(2)

.