Graficul roții
Cum sunt definite în această lucrare, un graf roată de ordinul
, uneori numit simplu un
-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
ș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
poate fi definită ca graful join
, unde
este graful singleton și
este graful ciclului, ceea ce o face un graf
conic.
Rețineți că există două convenții pentru indexarea grafurilor roată, unii autori (de ex, Gallian 2007), adoptând convenția că denotă graful roată pe
noduri.
Graful tetraedru (adică ) este izomorf cu
, iar
este izomorf cu graful tripartit complet
. În general, graful
-roată este scheletul unei piramide
.
este unul dintre cele două grafuri obținute prin eliminarea a două muchii din graful pentatopului
, celălalt fiind graful casei X.
Grafurile roată sunt grațioase (Frucht 1979).
Graful roată are dimensiunea grafică 2 pentru
(ș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.
Numărul de cicluri de graf în graful cu roți este dat de
, sau 7, 13, 21, 31, 43, 57, … (OEIS A002061) pentru
, 5, ….
Într-un graf de roată, butucul are gradul , iar celelalte noduri au gradul 3. Grafurile de roată au 3 conexiuni.
, unde
este graful complet de ordinul 4. Numărul cromatic al lui
este
![]() |
(1)
|
Ceea de graficul roții are polinomul cromatic
![]() |
(2)
|
.