Vertex-transitiv graf - Vertex-transitive graph

I det matematiske feltet grafteori er en toppunkt-transitiv graf en graf G der det, gitt noen to hjørner v ₁ og v ₂ av G , er noe automorfisme

{\ displaystyle f \ kolon G \ til G \}

slik at

{\ displaystyle f (v_ {1}) = v_ {2}. \}

Med andre ord, en graf er toppunkt-transitiv hvis dens automorfisme-gruppe virker transitt på toppunktene. En graf er toppunktet-transitive hvis og bare hvis dens graf komplement er, siden konsernet handlinger er identiske.

Hver symmetriske graf uten isolerte hjørner er toppunktovergang, og hver toppunktovergangsgraf er vanlig . Imidlertid er ikke alle toppunkt-transitive grafer symmetriske (for eksempel kantene på den avkortede tetraedronet ), og ikke alle vanlige grafer er toppunkt-transitive (for eksempel Frucht-grafen og Tietzes graf ).

Endelige eksempler

Kantene på den avkortede tetraederet danner en toppunkt-transitiv graf (også en Cayley-graf ) som ikke er symmetrisk .

Endelige toppunkt-transitive grafer inkluderer de symmetriske grafene (som Petersen-grafen , Heawood-grafen og toppunktene og kantene til de platoniske faste stoffene ). De endelige Cayley-grafene (som kubeforbundne sykluser ) er også toppunkt-transitive, i likhet med toppunktene og kantene til de arkimediske faste stoffene (selv om bare to av disse er symmetriske). Potočnik, Spiga og Verret har laget en folketelling av alle tilkoblede kubiske toppunkt-transitive grafer på maksimalt 1280 hjørner.

Selv om hver Cayley-graf er toppunkt-transitiv, finnes det andre toppunkt-transitive grafer som ikke er Cayley-grafer. Det mest kjente eksemplet er den Petersen grafen, men andre kan være konstruert inkludert linjediagram av kant-transitive ikke- todelte grafer med odde toppunktet grader.

Eiendommer

Den kant-tilkobling av en verteks-transitive kurve som er lik den grad d , mens toppunktet-tilkobling vil være minst 2 ( d + 1) / 3. Hvis graden er 4 eller mindre, eller grafen også er kantovergang , eller grafen er en minimal Cayley-graf , vil toppunktforbindelsen også være lik d .

Uendelige eksempler

Uendelige toppunkt-transitive grafer inkluderer:

uendelige stier (uendelig i begge retninger)
uendelige vanlige trær , f.eks. Cayley-grafen til den gratis gruppen
grafer over ensartede tessellasjoner (se en fullstendig liste over plane tessellasjoner ), inkludert alle fliser ved vanlige polygoner
uendelige Cayley-grafer
den Rado grafen

To tellbare toppunkt-transitive grafer kalles kvasi-isometrisk hvis forholdet mellom avstandsfunksjonene er begrenset nedenfra og ovenfra. En velkjent formodning uttalte at hver uendelig topp-transitiv graf er kvasi-isometrisk til en Cayley-graf . Et moteksempel ble foreslått av Diestel og Leader i 2001. I 2005 bekreftet Eskin, Fisher og Whyte moteksemplet.

Se også

Referanser

^ ^a ^b Godsil, Chris ; Royle, Gordon (2013) [2001], Algebraic Graph Theory , Graduate Texts in Mathematics , 207 , Springer, ISBN 978-1-4613-0163-9 CS1 maint: motløs parameter ( lenke ) .
^ Potočnik P., Spiga P. & Verret G. (2013), "Cubic vertex-transitive graphs on up to 1280 verteices", Journal of Symbolic Computation , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016 / j. jsc.2012.09.002 , S2CID 26705221 .
^ Lauri, Josef; Scapellato, Raffaele (2003), Emner i grafautorfismer og rekonstruksjon , London Mathematical Society Student Texts, 54 , Cambridge University Press, s. 44, ISBN 0-521-82151-7 , MR 1971819 . Lauri og Scapelleto krediterer denne konstruksjonen til Mark Watkins.
^ Babai, L. (1996), teknisk rapport TR-94-10 , University of Chicago, arkivert fra originalen 2010-06-11
^ Diestel, Reinhard; Leader, Imre (2001), "En gjetning angående en grense for ikke-Cayley-grafer" (PDF) , Journal of Algebraic Combinatorics , 14 (1): 17–25, doi : 10.1023 / A: 1011257718029 , S2CID 10927964 CS1 maint: motløs parameter ( lenke ) .
^ Eskin, Alex; Fisher, David; Whyte, Kevin (2005). "Kva-isometrier og stivhet av løsbare grupper". arXiv : math.GR/0511647 . .

Eksterne linker

Weisstein, Eric W. "Vertex-transitive graph" . MathWorld .
En folketelling av små sammenhengende kubiske toppunkt-transitive grafer . Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.

[Godsil01-1] Godsil, Chris ; Royle, Gordon (2013) [2001], Algebraic Graph Theory , Graduate Texts in Mathematics , 207 , Springer, ISBN 978-1-4613-0163-9 CS1 maint: motløs parameter ( lenke ) .

[2] Potočnik P., Spiga P. & Verret G. (2013), "Cubic vertex-transitive graphs on up to 1280 verteices", Journal of Symbolic Computation , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016 / j. jsc.2012.09.002 , S2CID 26705221 .

[3] Lauri, Josef; Scapellato, Raffaele (2003), Emner i grafautorfismer og rekonstruksjon , London Mathematical Society Student Texts, 54 , Cambridge University Press, s. 44, ISBN 0-521-82151-7 , MR 1971819 . Lauri og Scapelleto krediterer denne konstruksjonen til Mark Watkins.

[4] Babai, L. (1996), teknisk rapport TR-94-10 , University of Chicago, arkivert fra originalen 2010-06-11

[5] Diestel, Reinhard; Leader, Imre (2001), "En gjetning angående en grense for ikke-Cayley-grafer" (PDF) , Journal of Algebraic Combinatorics , 14 (1): 17–25, doi : 10.1023 / A: 1011257718029 , S2CID 10927964 CS1 maint: motløs parameter ( lenke ) .

[6] Eskin, Alex; Fisher, David; Whyte, Kevin (2005). "Kva-isometrier og stivhet av løsbare grupper". arXiv : math.GR/0511647 . .

Graffamilier definert av deres automorfismer
avstandstransitiv	→	avstands-vanlig	←	sterkt vanlig
↓
symmetrisk (bue-transitiv)	←	t -transitiv, $t \geq 2$		skjev-symmetrisk
↓
_{(hvis tilkoblet)} toppunkt- og kanttransitiv	→	kantovergang og vanlig	→	kantovergang
↓		↓		↓
toppunkt-transitiv	→	regelmessig	→	_{(hvis tosidig)} dobbeltregulert
↑
Cayley-graf	←	null-symmetrisk		asymmetrisk

Languages

In other projects