Kerék (gráfelmélet)

A gráfelméletben a W n kerék egy n csúcsú (n ≥ 4) gráf, amely egyetlen csúcsnak az ( n -1) -ciklus összes csúcsával való összekapcsolásával jön létre . A kerekek numerikus jelölése a szakirodalomban nem jól megalapozott - egyes szerzők n -t használnak a ciklus hosszának jelölésére, így W n-jük a fent definiált W n+1 grafikont jelenti [1] . Egy kerék ugyanúgy meghatározható, mint egy 1-csontváz( n -1)-szén piramis .

Képviselet beállítása

Legyen adott az {1,2,3,…,v} csúcsok halmaza. A gráfkerék éleinek halmaza egy halmazként ábrázolható: {{1,2},{1,3},…,{1,v},{2,3},{3,4},…, {v-1, v},{v,2}} [2] .

Tulajdonságok

A kerekek sík grafikonok , ezért egyedi beágyazással rendelkeznek a síkban. Bármelyik kerék Halin-gráf . Önkettősek – bármely kerék kettős grafikonja izomorf magával a kerékkel. A K 4 = W 4 kivételével bármely maximális síkgráf részgráfként W 5 vagy W 6 értéket tartalmaz .

Mindig van egy Hamilton-ciklus a kerékben , és a ciklusok száma W n - ben ( A002061 sorozat az OEIS -ben ).

n páratlan értékei esetén W n egy tökéletes gráf 3- as kromatikus számmal – a ciklus csúcsai két színnel színezhetők, a központi csúcsnak pedig egy harmadik színe lesz. Még n W n esetén is a kerék kromatikus száma 4, és ( n ≥ 6 esetén) nem lesz tökéletes gráf. A W 7 az egyetlen kerék, amely egységnyi távolsággráf az euklideszi síkon [3] .

A W n kerék kromatikus polinomja :

A matroidelméletben két különösen fontos fajta matroid létezik, a kerekek és az örvények , amelyek mindkettő kerékgráfokból származik. A k -kerék matroid egy gráf matroidW k+1 kerék , a k -örvény matroidot pedig a k -kerék matroidból kapjuk úgy , hogy a külső ciklust (peremet) olyan függetlennek nyilvánítjuk, mint annak átfeszítő fái .

A W 6 kerék ellenpéldát ad Paul Erdős Ramsey-elméletbeli sejtésére – azt sejtette, hogy egy teljes gráfban van a legkisebb Ramsey-szám az azonos kromatikus számmal rendelkező gráfok közül. Faudree és McKay (Faudree, McKay, 1993) azonban kimutatta, hogy W 6 esetén a Ramsey-szám 17, míg egy teljes , azonos kromatikus számmal rendelkező K 4 gráfnál a Ramsey-szám 18 [4] . Így bármely 17 csúcsú G gráf esetén vagy maga G , vagy annak komplementere tartalmazza a W 6 -ot részgráfként, míg sem a 17 csúcsú Paley gráf , sem annak komplementere nem tartalmaz K 4 -et .

Jegyzetek

1. ↑ Weisstein, Eric W. Wheel Graph  a Wolfram MathWorld weboldalán .
2. ↑ Richard J. Trudeau. Bevezetés a gráfelméletbe. — Javított, kibővített republication. New York: Dover Pub. - P. 56. - ISBN 978-0-486-67870-2 .
3. ↑ Fred Buckley, Frank Harary. A kerék euklideszi dimenziójáról // Grafikonok és kombinatorika. - 1988. - V. 4 , sz. 1 . — S. 23–30 . - doi : 10.1007/BF01864150 .
4. ↑ Ralph J. Faudree, Brendan D. McKay. Erdős és a Ramsey-szám r ( W 6 ) sejtése // J. Kombinatorikus matematika. és a Kombinatorikus számítástechnika. - 1993. - T. 13 . – S. 23–31 .