A szimmetrikus gráf (vagy az ívekre vonatkozó tranzitív gráf ) egy G gráf , amely bármely két szomszédos csúcspárra, amelyeknek u 1 - v 1 és u 2 - v 2 van, van egy automorfizmus :
f : V ( G ) → V ( G )oly módon, hogy:
f ( u 1 ) = u 2 és f ( v 1 ) = v 2 . [egy]Más szóval, egy gráf szimmetrikus, ha automorfizmuscsoportja tranzitívan hat szomszédos csúcsok rendezett párjaira (tehát minden élen mintha orientációjuk lenne). [2] Az ilyen gráfokat néha 1-tranzitívnak is nevezik az ívek tekintetében [2] vagy flag-tranzitívnak . [3]
Definíció szerint az izolált csúcsok nélküli szimmetrikus gráfoknak csúcstranzitívnak is kell lenniük . [1] Mivel a fenti definíció szerint az élek egyikről a másikra fordíthatók, a szimmetrikus gráfoknak is éltranzitívnak kell lenniük . Az éltranzitív gráf azonban nem feltétlenül szimmetrikus, mivel a -b leképezhető c - d -re , de d - c -re nem . A félszimmetrikus gráfok például éltranzitívak és szabályosak , de nem csúcstranzitívak.
Minden összekapcsolt szimmetrikus gráfnak csúcstranzitívnak és éltranzitívnak is kell lennie, és a páratlan fokú gráfokra fordítva igaz. [3] A páros fokokhoz azonban léteznek olyan összekapcsolt gráfok, amelyek csúcstranzitívak és éltranzitívak is, de nem szimmetrikusak. [4] Az ilyen gráfokat féltranzitívnak nevezzük . [5] A legkisebb összefüggő féltranzitív gráf a Holt-gráf , amelynek 4-es foka és 27 csúcsa van. [1] [6] Megtévesztő, hogy egyes szerzők a "szimmetrikus gráf" kifejezést használják olyan gráfokra, amelyek csúcstranzitívak és éltranzitívak is. Egy ilyen meghatározás magában foglalja a félig tranzitív gráfokat is, amelyeket a fenti definíció kizár.
A távolság-tranzitív gráf olyan gráf, amelyben ahelyett, hogy egységnyi távolságra lennének, a szomszédos csúcsok azonos rögzített távolságra vannak. Az ilyen gráfok definíció szerint szimmetrikusak. [egy]
A t -ívet t +1 csúcsokból álló sorozatként definiáljuk úgy , hogy bármely két egymást követő csúcs szomszédos, és a csúcsok ismétlődése legkorábban 2 lépés után következhet be. Egy gráfot t -tranzitívnak mondunk , ha az automorfizmuscsoport tranzitívan hat a t -ívekre, de nem a ( t +1) -ívekre. Mivel az 1-ívek csak élek, bármely 3-as vagy annál nagyobb fokú szimmetrikus gráfnak t - tranzitívnak kell lennie valamilyen t esetén, és t értéke felhasználható gráfok osztályozására. A kocka például 2-tranzitív. [egy]
A szimmetriafeltételek kombinálása azzal a feltétellel, hogy a gráf köbös (vagyis minden csúcs 3-as fokozatú), elég erős feltételt generál ahhoz, hogy minden ilyen gráf elég ritka a felsoroláshoz. Foster listája és kiterjesztései ilyen listákat adnak. [7] Foster listáját az 1930-as években Ronald Foster indította el a Bell Labsnál töltött ideje alatt , [8] és 1988-ban (amikor Foster 92 éves volt [1] ) Foster listája (az összes szimmetrikus köbös gráf lista 512 csúcsig, akkoriban ismert) könyvként jelent meg. [9] A lista első tizenhárom eleme legfeljebb 30 csúcsú köbös szimmetrikus gráf [10] [11] (ebből tíz távolságtranzitív ), az alábbi táblázatban látható.
| Csúcsok | Átmérő | Heveder | Grafikon | Megjegyzések |
|---|---|---|---|---|
| négy | egy | 3 | teljes gráf K 4 | távolság tranzitív, 2-tranzitív |
| 6 | 2 | négy | teljes kétrészes gráf K 3,3 | távolság tranzitív, 3-tranzitív |
| nyolc | 3 | négy | kocka csúcsai és élei | távolság tranzitív, 2-tranzitív |
| tíz | 2 | 5 | Petersen grófja | távolság tranzitív, 3-tranzitív |
| tizennégy | 3 | 6 | Heawood grófja | távolság tranzitív, 4-tranzitív |
| 16 | négy | 6 | Möbius-Cantor gráf | 2-tranzitív |
| tizennyolc | négy | 6 | Pappa gróf | távolság tranzitív, 3-tranzitív |
| húsz | 5 | 5 | a dodekaéder csúcsai és élei | távolság tranzitív, 2-tranzitív |
| húsz | 5 | 6 | Desargues gróf | távolság tranzitív, 3-tranzitív |
| 24 | négy | 6 | Nauru gráf ( általánosított Petersen-gráf G(12,5)) | 2-tranzitív |
| 26 | 5 | 6 | grafikon F26A [11] | 1-tranzitív |
| 28 | négy | 7 | Coxeter grófja | távolság tranzitív, 3-tranzitív |
| harminc | négy | nyolc | Thatta-Coxeter grófja | távolság tranzitív, 5-tranzitív |
További jól ismert szimmetrikus köbös gráfok a Dick -gráf , a Foster-gráf és a Biggs-Smith-gráf . A fentiekben tíz távolság-tranzitív grafikon található. A Foster és a Biggs-Smith gráfokkal együtt ezek az egyetlen távolságtranzitív gráfok.
A nem köbös szimmetrikus gráfok magukban foglalják a ciklusokat (2 fok), a teljes gráfokat (4 és annál nagyobb fokok 5 vagy több csúcstal), a hiperkocka gráfokat (4 és annál nagyobb fokok 16 vagy több csúcstal), valamint a csúcsok és a csúcsok által alkotott gráfokat. az oktaéder , ikozaéder , kuboktaéder és ikozidodekaéder élei . A Rado gráf példát ad egy végtelen számú csúcsú és végtelen fokos szimmetrikus gráfra.
A szimmetrikus gráf csúcsösszeköthetősége mindig egyenlő a d fokkal . [3] Ezzel szemben az általános csúcstranzitív gráfok esetében a csúcsösszeköthetőséget alul 2( d +1)/3 határolja. [2]
A 3-as vagy magasabb fokú t -tranzitív gráf kerülete legalább 2( t -1). Nincsenek azonban véges t -tranzitív 3-as vagy magasabb fokú gráfok t ≥ 8 esetén. Pontosan három fok esetén (köbös szimmetrikus gráfok), t ≥ 6 -ra nincsenek gráfok .