Graficul varf-tranzitiv

În teoria grafurilor, un graf tranzitiv la vârf este un graf G astfel încât pentru oricare două vârfuri v 1 și v 2 ale grafului G există un automorfism

astfel încât

Cu alte cuvinte, un graf este varf-tranzitiv dacă grupul său de automorfism acționează tranzitiv în raport cu vârfurile [1] . Un grafic este tranzitiv la vârf dacă și numai dacă rezultatele automorfismelor complementului său sunt identice.

Orice graf simetric fără vârfuri izolate este tranzitiv la vârf, iar orice graf tranzitiv la vârf este regulat . Cu toate acestea, nu toate graficele tranzitive de vârf sunt simetrice (de exemplu, muchiile unui tetraedru trunchiat ) și nu toate graficele obișnuite sunt tranzitive de vârf (de exemplu, graficul Frucht și graficul Tietze ).

Exemple de grafice finite

Setul de grafice tranzitive de vârf finite include grafice simetrice (cum ar fi graficul Petersen , graficul Heawood și vârfurile și muchiile poliedrelor regulate ). Graficele finite Cayley (cum ar fi ciclurile cube ) sunt tranzitive la vârf, la fel ca vârfurile și muchiile unui solid arhimedian (deși doar 2 dintre ele sunt simetrice). Potočnik, Spiga și Verret au creat un recensământ al tuturor graficelor cubice conectate (adică cu vârfuri de gradul 3) tranzitive de vârf cu numărul de vârfuri care nu depășește 1280 [2] .

Proprietăți

Conectivitatea muchiilor unui graf tranzitiv de vârf este egală cu gradul d , în timp ce conectivitatea de vârf va fi de cel puțin 2( d +1)/3 [3] . Dacă gradul este 4 sau mai mic, sau graficul este, de asemenea , tranzitiv la muchie , sau graficul este un grafic Cayley minim , atunci conectivitatea vârfurilor va fi d [4] .

Exemple de grafice infinite

Graficele infinite tranzitive de vârf includ:

Două grafice tranzitive de vârf numărabile sunt numite cvasiizometrice dacă raportul funcțiilor lor de distanță este mărginit de jos și de sus. O presupunere bine-cunoscută afirmă că orice graf tranzitiv de vârf infinit este cvasiizomorf cu graful Cayley . Un contraexemplu a fost prezentat de Reinhard Diesel și Imre Leader în 2001 [5] . În 2005, Eskin, Fisher și Whyte au confirmat corectitudinea contraexemplului [6] .

Vezi și

Note

  1. ↑ Chris Godsil, Gordon Royle. Teoria algebrică a graficelor. - New York: Springer-Verlag, 2001. - T. 207 .
  2. ↑ Potočnik P., Spiga P. și Verret G. (2012), Cubic vertex-tranzitive graphs on up to 1280 vertices , Journal of Symbolic Computation 
  3. ↑ Godsil, C. și Royle, G. Teoria graficelor algebrice. — Springer Verlag, 2001.
  4. ↑ Babai, L. Raport tehnic TR-94-10. - Universitatea din Chicago, 1996 . Preluat la 29 august 2010. Arhivat din original la 11 iunie 2010.
  5. ↑ Reinhard Diesel, Lider Imre. O conjectură privind o limită a graficelor non-Cayley // Journal of Algebraic Combinatorics. - 2001. - T. 14 , nr. 1 . — S. 17–25 . - doi : 10.1023/A:1011257718029 .
  6. ↑ Alex Eskin, David Fisher, Kevin Whyte. Cvasiizometrii și rigiditatea grupărilor solubile. — 2005.

Link -uri