Graficul simetric

Un grafic simetric (sau un grafic tranzitiv în raport cu arce ) este un grafic G , pentru oricare două perechi de vârfuri adiacente dintre care u 1 - v 1 și u 2 - v 2 există un automorfism :

f  : V ( G ) → V ( G )

astfel încât:

f ( u 1 ) = u 2 și f ( v 1 ) = v 2 . [unu]

Cu alte cuvinte, un graf este simetric dacă grupul său de automorfism acționează tranzitiv pe perechi ordonate de vârfuri adiacente (astfel, pe toate muchiile ca și cum ar avea o orientare). [2] Astfel de grafice sunt uneori numite și 1-tranzitive în raport cu arce [2] sau flag-tranzitive . [3]

Prin definiție, graficele simetrice fără vârfuri izolate trebuie să fie și tranzitive la vârf . [1] Deoarece, prin definiția de mai sus, muchiile pot fi translatate de la una la alta, graficele simetrice trebuie să fie și ele tranzitive . Totuși, un graf tranzitiv de muchie nu este neapărat simetric, deoarece a - b poate fi mapat la c - d , dar nu și la d - c . Graficele semisimetrice , de exemplu, sunt tranzitive la margine și regulate , dar nu tranzitive la vârf.

Orice graf simetric conectat trebuie să fie atât tranzitiv la vârf, cât și tranzitiv la margine, iar inversul este valabil pentru graficele de grad impar. [3] Cu toate acestea, pentru grade egale, există grafuri conectate care sunt atât tranzitive la vârf, cât și tranzitive la margine, dar nu simetrice. [4] Astfel de grafice sunt numite semi-tranzitive . [5] Cel mai mic graf semi-tranzitiv conectat este graful Holt , care are gradul 4 și 27 de vârfuri. [1] [6] În mod confuz, unii autori folosesc termenul de „graf simetric” pentru graficele care sunt atât tranzitive la vârf, cât și tranzitive la margine. O astfel de definiție include grafice semi-tranzitive, care sunt excluse de definiția de mai sus.

Un grafic tranzitiv la distanță  este un grafic în care, în loc să fie unitate de distanță, vârfurile adiacente se află la aceeași distanță fixă. Astfel de grafice sunt, prin definiție, simetrice. [unu]

Un t -arc este definit ca o succesiune de t +1 vârfuri astfel încât oricare două vârfuri consecutive sunt adiacente, iar repetarea vârfurilor poate avea loc nu mai devreme după 2 pași. Se spune că un grafic este t -tranzitiv dacă grupul de automorfism acționează tranzitiv asupra arcurilor t , dar nu asupra arcurilor ( t +1). Deoarece arcurile 1 sunt doar muchii, orice grafic simetric de grad 3 sau mai mare trebuie să fie t -tranzitiv pentru unele t , iar valoarea lui t poate fi folosită pentru a clasifica grafice. Cubul este 2-tranzitiv, de exemplu. [unu]

Exemple

Combinarea condițiilor de simetrie cu condiția ca graficul să fie cubic (adică toate vârfurile au gradul 3) generează o condiție suficient de puternică încât toate astfel de grafice să fie suficient de rare pentru a le enumera. Lista lui Foster și extensiile sale oferă astfel de liste. [7] Lista lui Foster a fost începută în anii 1930 de Ronald Foster în timpul petrecut la Bell Labs , [8] și în 1988 (când Foster avea 92 de ani [1] ) Lista lui Foster (o listă a tuturor graficelor cubice simetrice până la 512 vârfuri, cunoscut la acea vreme) a fost publicat ca o carte. [9] Primele treisprezece elemente ale listei sunt grafice simetrice cubice cu până la 30 de vârfuri [10] [11] (zece dintre ele sunt tranzitive la distanță ), sunt date în tabelul de mai jos

Vârfurile Diametru Circumferinţă Grafic Note
patru unu 3 completați graficul K 4 distanta tranzitiva, 2-tranzitiva
6 2 patru graf bipartit complet K 3,3 distanta tranzitiva, 3-tranzitiva
opt 3 patru vârfurile și muchiile unui cub distanta tranzitiva, 2-tranzitiva
zece 2 5 conte de Petersen distanta tranzitiva, 3-tranzitiva
paisprezece 3 6 Contele de Heawood distanta tranzitiva, 4-tranzitiva
16 patru 6 Graficul Möbius-Cantor 2-tranzitiv
optsprezece patru 6 Contele Pappa distanta tranzitiva, 3-tranzitiva
douăzeci 5 5 vârfurile și muchiile dodecaedrului distanta tranzitiva, 2-tranzitiva
douăzeci 5 6 Contele Desargues distanta tranzitiva, 3-tranzitiva
24 patru 6 graficul Nauru ( graficul generalizat Petersen G(12,5)) 2-tranzitiv
26 5 6 graficul F26A [11] 1-tranzitiv
28 patru 7 Contele de Coxeter distanta tranzitiva, 3-tranzitiva
treizeci patru opt Contele de Thatta-Coxeter distanta tranzitiva, 5-tranzitiva

Alte grafice cubice simetrice binecunoscute sunt graficul Dick , graficul Foster și graficul Biggs-Smith . Zece grafice tranzitive la distanță sunt enumerate mai sus. Împreună cu graficul Foster și graficul Biggs-Smith, acestea sunt singurele grafice tranzitive la distanță.

Graficele simetrice necubice includ cicluri (grade de 2), grafice complete (grade de 4 și mai sus cu 5 sau mai multe vârfuri), grafice hipercubice (grade de 4 și mai sus cu 16 sau mai multe vârfuri) și grafice formate din vârfuri și marginile octaedrului , icosaedrului , cuboctaedrului și icosidodecaedrului . Graficul Rado oferă un exemplu de grafic simetric cu un număr infinit de vârfuri și un grad infinit.

Proprietăți

Conectivitatea vârfurilor unui graf simetric este întotdeauna egală cu gradul d . [3] În schimb, pentru graficele tranzitive de vârf generale, conectivitatea vârfurilor este mărginită mai jos de 2( d +1)/3. [2]

Un grafic t -tranzitiv de gradul 3 sau mai mare are circumferința de cel puțin 2( t -1). Cu toate acestea, nu există grafice t -tranzitive finite de gradul 3 sau mai mare pentru t ≥ 8. În cazul exact de gradul trei (grafice simetrice cubice), nu există grafice pentru t ≥ 6.

Vezi și

Note

  1. 1 2 3 4 5 6 Biggs, Norman. Teoria algebrică a graficelor. — al 2-lea. - Cambridge: Cambridge University Press, 1993. - S. 118-140. — ISBN 0-521-45897-8 .
  2. 1 2 3 Chris Godsil, Gordon Royle. Teoria graficelor algebrice . - New York: Springer, 2001. - P.  59 . — ISBN 0-387-95220-9 .
  3. 1 2 3 L Babai. Manual de combinatorică / R Graham, M Groetschel, L Lovasz. — Elsevier, 1996.
  4. Bouwer, Z. „Vertex and Edge Transitive, But Not 1-Traitive Graphs”. Canada. Matematică. Taur. 13, 231-237, 1970.
  5. Gross, JL și Yellen, J. Handbook of Graph Theory. - CRC Press, 2004. - P. 491. - ISBN 1-58488-090-2 .
  6. Derek F. Holt. Un grafic care este tranzitiv la margine, dar nu este tranzitiv în arc  // ​​Journal of Graph Theory. - 1981. - V. 5 , nr. 2 . - S. 201-204 . - doi : 10.1002/jgt.3190050210 . .
  7. Marston Conder , Grafice simetrice trivalente pe până la 768 de vârfuri Arhivat la 15 iunie 2011 la Wayback Machine , J. Combin. Matematică. Combina. Comput, voi. 20, pp. 41-63
  8. Foster, R.M. „Circuite geometrice ale rețelelor electrice”. Tranzacții ale Institutului American de Ingineri Electrici 51 , 309-317, 1932.
  9. „The Foster Census: RM Foster’s Census of Connected Symmetric Trivalent Graphs”, de Ronald M. Foster, IZ Bouwer, WW Chernoff, B. Monson și Z. Star (1988) ISBN 0-919611-19-2
  10. Biggs, p. 148
  11. 1 2 Weisstein, Eric W., „ Cubic Symmetric Graph Arhivat 5 ianuarie 2011 la Wayback Machine ”, de la Wolfram MathWorld.

Link -uri