Vertex-transitiv graf

Inom grafteorin är en vertextransitiv graf en graf G så att det för två valfria hörn v 1 och v 2 i grafen G existerar en automorfism

Så att

Med andra ord, en graf är vertextransitiv om dess automorfismgrupp agerar transitivt med avseende på hörn [1] . En graf är vertextransitiv om och endast om resultaten av automorfismer av dess komplement är identiska.

Varje symmetrisk graf utan isolerade hörn är vertextransitiv, och alla vertextransitiva grafer är regelbundna . Men inte alla vertextransitiva grafer är symmetriska (till exempel kanterna på en trunkerad tetraeder ), och inte alla vanliga grafer är vertextransitiva (till exempel Frucht-grafen och Tietze-grafen ).

Exempel på finita grafer

Uppsättningen av ändliga vertex-transitiva grafer inkluderar symmetriska grafer (som Petersen -grafen , Heawood-grafen och hörn och kanter på vanliga polyedrar ). Finita Cayley-grafer (som kubade cykler ) är vertextransitiva, liksom hörn och kanter på ett arkimedeskt fast ämne (även om bara två av dem är symmetriska). Potočnik, Spiga och Verret skapade en räkning av alla anslutna kubiska (det vill säga med hörn av grad 3) vertextransitiva grafer med antalet hörn som inte överstiger 1280 [2] .

Egenskaper

Kantanslutningen för en vertextransitiv graf är lika med graden d , medan vertexanslutningen kommer att vara minst 2( d +1)/3 [3] . Om graden är 4 eller mindre, eller om grafen också är kanttransitiv , eller om grafen är en minimal Cayley-graf , kommer vertexanslutningen att vara d [4] .

Exempel på oändliga grafer

Oändliga vertextransitiva grafer inkluderar:

Två räknebara vertextransitiva grafer kallas kvasi-isometriska om förhållandet mellan deras avståndsfunktioner är avgränsat underifrån och ovanför. En välkänd gissning säger att varje oändlig vertex-transitiv graf är kvasi-isomorf till Cayley-grafen . Ett motexempel presenterades av Reinhard Diestel och Imre Leader 2001 [5] . År 2005 bekräftade Eskin, Fisher och Whyte riktigheten av motexemplet [6] .

Se även

Anteckningar

  1. ↑ Chris Godsil, Gordon Royle. Algebraisk grafteori. - New York: Springer-Verlag, 2001. - T. 207 .
  2. ↑ Potočnik P., Spiga P. och Verret G. (2012), Cubic vertex-transitiva grafer på upp till 1280 hörn , Journal of Symbolic Computation 
  3. ↑ Godsil, C. och Royle, G. Algebraisk grafteori. — Springer Verlag, 2001.
  4. ↑ Babai, L. Teknisk rapport TR-94-10. - University of Chicago, 1996 . Hämtad 29 augusti 2010. Arkiverad från originalet 11 juni 2010.
  5. ↑ Reinhard Diestel, Imre Leader. En gissning om en gräns för icke-Cayley-grafer // Journal of Algebraic Combinatorics. - 2001. - T. 14 , nr. 1 . — S. 17–25 . - doi : 10.1023/A:1011257718029 .
  6. ↑ Alex Eskin, David Fisher, Kevin Whyte. Kvasi-isometrier och stelhet hos lösbara grupper. — 2005.

Länkar