Roata (teoria graficelor)

În teoria grafurilor, o roată W n este un grafic cu n vârfuri (n ≥ 4), format prin legătura unui singur vârf cu toate vârfurile ciclului ( n -1 ) . Denumirea numerică a roților din literatură nu este bine stabilită - unii autori folosesc n pentru a desemna lungimea ciclului, astfel încât W n înseamnă graficul W n+1 așa cum este definit mai sus [1] . O roată poate fi definită în același mod ca un schelet( n -1)-piramida cărbunelui .

Setați reprezentarea

Să fie dată mulțimea de vârfuri {1,2,3,…,v}. Setul de muchii ale roții grafice poate fi reprezentat ca o mulțime {{1,2},{1,3},...,{1,v},{2,3},{3,4},..., {v-1, v},{v,2}} [2] .

Proprietăți

Roțile sunt grafice plane și, prin urmare, au o încorporare unică în plan. Orice roată este un grafic Halin . Ele sunt auto-duale - graficul dual al oricărei roți este izomorf cu roata în sine. Orice graf planar maximal, altul decât K 4 = W 4 , conține fie W 5 , fie W 6 ca subgraf .

Există întotdeauna un ciclu hamiltonian în roată și numărul de cicluri din W n este (secvența A002061 în OEIS ).

Pentru valorile impare ale lui n , W n este un grafic perfect cu număr cromatic 3 — vârfurile ciclului pot fi colorate în două culori, iar vârful central va avea o a treia culoare. Pentru n W n , roata are numărul cromatic 4 și (pentru n ≥ 6) nu va fi un grafic perfect. W 7 este singura roată care este un grafic de distanță unitară pe planul euclidian [3] .

Polinomul cromatic al roții W n este:

Există două tipuri deosebit de importante de matroizi în teoria matroidelor, roțile și vârtejurile , ambele derivate din graficele roților. Matroidul k -wheel este un matroid graficroata W k+1 , iar matroida k -vortex este obținută din matroida k -roată prin declararea ciclului exterior (rima) la fel de independent ca arborii care se întind .

Roata W 6 oferă un contraexemplu pentru conjectura lui Paul Erdő în teoria Ramsey - el a presupus că un grafic complet are cel mai mic număr Ramsey dintre toate graficele cu același număr cromatic. Cu toate acestea, Faudree și McKay (Faudree, McKay, 1993) au arătat că pentru W 6 numărul Ramsey este 17, în timp ce pentru un grafic complet K 4 cu același număr cromatic, numărul Ramsey este 18 [4] . Astfel, pentru orice graf cu 17 vârfuri G , fie G însuși, fie complementul său conține W 6 ca subgraf, în timp ce nici graficul Paley cu 17 vârfuri și nici complementul său nu conțin K 4 .

Note

1. ^ Weisstein , Eric W. Wheel Graph  pe site- ul Wolfram MathWorld .
2. ↑ Richard J. Trudeau. Introducere în teoria grafurilor. — Republicare corectată, extinsă. New York: Dover Pub. - P. 56. - ISBN 978-0-486-67870-2 .
3. ↑ Fred Buckley, Frank Harary. Despre dimensiunea euclidiană a unei roți // Grafice și combinatorie. - 1988. - V. 4 , nr. 1 . — S. 23–30 . - doi : 10.1007/BF01864150 .
4. ↑ Ralph J. Faudree, Brendan D. McKay. O conjectură a lui Erdős și a numărului Ramsey r ( W 6 ) // J. Combinatorial Math. și Calculator combinatoriu. - 1993. - T. 13 . — S. 23–31 .