Kerékgráf

Kerékgráf
Példák kerékgráfokra
Példák kerékgráfokra

Csúcsok száman
Élek száma2(n − 1)
Átmérő2, ha n>4
1, ha n=4
Derékbőség3
Kromatikus szám3, ha n páratlan
4, ha n páros
Spektrum
EgyébHamiltoni
Önduális
Síkgráf
JelölésWn

A matematika, azon belül a gráfelmélet területén egy kerékgráf (wheel graph) olyan gráf, amit egy körgráf univerzális csúccsal való bővítésével kapunk. Az n csúcsú kerékgráf tekinthető az (n−1)-szögű gúla 1-vázának is. Egyes szerzők[1] Wn-nel jelölik az n csúcsú (n ≥ 4) kerékgráfokat; más szerzők[2] viszont az n „küllőjű”, azaz n+1 csúcsú (n ≥ 3) kerékgráfot jelölik Wn-nel. Ebben a szócikkben a két jelölés közül az elsőt használjuk.

Konstrukció

Az {1,2,3,…,v} csúcshalmazt tekintve a kerékgráf élhalmaza a következő felsorolással adható meg: {{1,2},{1,3},…,{1,v},{2,3},{3,4},…,{v-1,v},{v,2}}.[3]

Tulajdonságai

A kerékgráfok síkgráfok, továbbá Halin-gráfok. Önduálisak: bármely kerékgráf duálisa egy vele izomorf gráf. Minden maximális síkgráf részgráfként tartalmazza vagy a W5, vagy a W6 kerékgráfot; a K4 = W4 esettől eltekintve.

A kerékgráf mindig tartalmaz Hamilton-kört, továbbá a Wn-ben pontosan kör található (A002061 sorozat az OEIS-ben).


A W4 kerékgráf 7 köre.

Páratlan n-ekre a Wn perfekt gráf, kromatikus száma 3: a kör szélén lévő csúcsok váltakozva két színnel színezhetők, a közepének pedig egy harmadik színt kell adni. Páros n-ekre a Wn kromatikus száma 4, és (ha n ≥ 6) nem perfekt. A W7 az egyetlen kerékgráf, ami az euklideszi síkon egységtávolsággráf.[4]

A Wn kerékgráf kromatikus polinomja:

A matroidok elméletében a „kerékmatroidok” (wheel matroids) és az „örvénymatroidok” (whirl matroids) két különösen fontos matroidosztályt alkotnak – mindkettő a kerékgráfokból származik. A k-kerék matroid a Wk+1 kerék grafikus matroidja, míg a k-örvény matroid a k-kerékből származik, ha a kerék külső körét és annak összes feszítőfáját függetlennek tekintjük.

A W6 kerékgráf Erdős Pál egy Ramsey-elméleti sejtésére szolgáltatott ellenpéldát: Erdős úgy sejtette, hogy az azonos kromatikus számú gráfok közül a teljes gráfnak legkisebb a Ramsey-száma, de Faudree és McKay (1993) megmutatták, hogy a W6 Ramsey-száma 17, míg a vele azonos kromatikus számú K4 teljes gráf Ramsey-száma 18.[5] Tehát bármely 17 csúcsú G gráf esetében vagy G-nek vagy a komplementerének tartalmaznia kell a W6-t részgráfként, míg például sem a 17 csúcsú Paley-gráf, sem a komplementere nem tartalmaz K4-et.

Fordítás

  • Ez a szócikk részben vagy egészben a Wheel graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

  1. Weisstein, Eric W.: Wheel Graph (angol nyelven). Wolfram MathWorld
  2. Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications, 7th ed., McGraw-Hill, p. 655.
  3. Trudeau, Richard J.. Introduction to Graph Theory, Corrected, enlarged republication., New York: Dover Pub., 56. o. (1993). ISBN 978-0-486-67870-2. Hozzáférés ideje: 2012. augusztus 8. 
  4. Buckley, Fred & Harary, Frank (1988), "On the euclidean dimension of a wheel", Graphs and Combinatorics 4 (1): 23–30, DOI 10.1007/BF01864150.
  5. Faudree, Ralph J. & McKay, Brendan D. (1993), "A conjecture of Erdős and the Ramsey number r(W6)", J. Combinatorial Math. and Combinatorial Comput. 13: 23–31, <http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz>.