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]
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.
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.