Csúcs-tranzitív gráf

A gráfelméletben a csúcstranzitív gráf egy olyan G gráf , amelyben a G gráf bármely két v 1 és v 2 csúcsára létezik automorfizmus .

oly módon, hogy

Más szóval, egy gráf csúcstranzitív, ha az automorfizmuscsoportja tranzitívan hat a csúcsokhoz [1] . Egy gráf akkor és csak akkor csúcstranzitív, ha komplementere automorfizmusának eredménye azonos.

Bármely szimmetrikus gráf izolált csúcsok nélkül csúcstranzitív, és minden csúcstranzitív gráf szabályos . Azonban nem minden csúcstranzitív gráf szimmetrikus (például egy csonka tetraéder élei ), és nem minden reguláris gráf csúcstranzitív (például a Frucht-gráf és a Tietze-gráf ).

Példák véges gráfokra

A véges csúcstranzitív gráfok halmaza szimmetrikus gráfokat tartalmaz (például a Petersen -gráfot , a Heawood-gráfot és a szabályos poliéderek csúcsait és éleit ). A véges Cayley-gráfok (mint például a kockaciklusok ) csúcstranzitívak, csakúgy, mint az arkhimédeszi test csúcsai és élei (bár közülük csak 2 szimmetrikus). Potočnik, Spiga és Verret elkészítették az összes összefüggő köbös (vagyis 3-as fokú csúcsú) csúcstranzitív gráf összeírását, a csúcsok száma nem haladja meg az 1280-at [2] .

Tulajdonságok

Egy csúcstranzitív gráf élösszeköthetősége egyenlő a d fokkal , míg a csúcsösszeköthetőség legalább 2( d +1)/3 [3] . Ha a fokszám 4 vagy kisebb, vagy a gráf éltranzitív is , vagy a gráf egy minimális Cayley-gráf , akkor a csúcsösszeköthetőség d lesz [4] .

Példák végtelen gráfokra

A végtelen csúcs-tranzitív gráfok közé tartoznak:

Két megszámlálható csúcstranzitív gráfot kváziizometrikusnak nevezünk , ha távolságfüggvényeik aránya alulról és felülről korlátos. Egy jól ismert sejtés azt állítja, hogy bármely végtelen csúcs-tranzitív gráf kvázi izomorf a Cayley gráfhoz . Ellenpéldát mutatott be Reinhard Diestel és Imre Leader 2001-ben [5] . 2005-ben Eskin, Fisher és Whyte megerősítette az ellenpélda helyességét [6] .

Lásd még

Jegyzetek

  1. ↑ Chris Godsil, Gordon Royle. Algebrai gráfelmélet. - New York: Springer-Verlag, 2001. - T. 207 .
  2. ↑ Potočnik P., Spiga P. és Verret G. (2012), Cubic vertex-tranzitive graphs on up to 1280 vertices , Journal of Symbolic Computation 
  3. ↑ Godsil, C. és Royle, G. Algebrai gráfelmélet. — Springer Verlag, 2001.
  4. ↑ Babai, L. Műszaki Jelentés TR-94-10. - Chicagói Egyetem, 1996 . Letöltve: 2010. augusztus 29. Az eredetiből archiválva : 2010. június 11.
  5. ↑ Reinhard Diestel, Imre Vezető. Egy sejtés a nem-Cayley-gráfok határértékéről // Journal of Algebraic Combinatorics. - 2001. - T. 14 , sz. 1 . – S. 17–25 . - doi : 10.1023/A:1011257718029 .
  6. ↑ Alex Eskin, David Fisher, Kevin Whyte. A megoldható csoportok kváziizometriái és merevsége. – 2005.

Linkek