En symmetrisk graf (eller en graf transitiv med avseende på bågar ) är en graf G , för två par av angränsande hörn av vilka u 1 - v 1 och u 2 - v 2 det finns en automorfism :
f : V ( G ) → V ( G )Så att:
f ( u 1 ) = u 2 och f ( v 1 ) = v 2 . [ett]Med andra ord är en graf symmetrisk om dess automorfismgrupp verkar transitivt på ordnade par av angränsande hörn (alltså på alla kanter som om de hade en orientering). [2] Sådana grafer kallas ibland också 1-transitiv med avseende på bågar [2] eller flaggtransitiv . [3]
Per definition måste symmetriska grafer utan isolerade hörn också vara vertextransitiva . [1] Eftersom, enligt definitionen ovan, kanter kan översättas från en till en annan, måste symmetriska grafer också vara kanttransitiva . En kanttransitiv graf är dock inte nödvändigtvis symmetrisk, eftersom a - b kan mappas till c - d , men inte till d - c . Semisymmetriska grafer , till exempel, är kanttransitiva och reguljära , men inte vertextransitiva.
Varje ansluten symmetrisk graf måste vara både vertextransitiv och kanttransitiv, och det omvända gäller för grafer med udda grad. [3] Men för jämna grader finns det sammankopplade grafer som är både vertextransitiva och kanttransitiva, men inte symmetriska. [4] Sådana grafer kallas semi-transitiva . [5] Den minsta sammankopplade semi-transitiva grafen är Holt-grafen , som har grader 4 och 27 hörn. [1] [6] Förvirrande nog använder vissa författare termen "symmetrisk graf" för grafer som är både vertextransitiv och kanttransitiv. En sådan definition inkluderar semi-transitiva grafer, som utesluts av definitionen ovan.
En avståndstransitiv graf är en graf där, istället för att vara enhetsavstånd, angränsande hörn är på samma fasta avstånd. Sådana grafer är per definition symmetriska. [ett]
En t -båge definieras som en sekvens av t +1 hörn så att två på varandra följande hörn ligger intill varandra, och upprepning av hörn kan ske inte tidigare än efter 2 steg. En graf sägs vara t -transitiv om automorfismgruppen verkar transitivt på t -bågar men inte på ( t +1)-bågar. Eftersom 1-bågar bara är kanter måste varje symmetrisk graf av grad 3 eller mer vara t -transitiv för vissa t , och värdet på t kan användas för att klassificera grafer. Kuben är till exempel 2-transitiv. [ett]
Att kombinera symmetrivillkoren med villkoret att grafen är kubisk (det vill säga alla hörn har grad 3) genererar ett tillräckligt starkt villkor för att alla sådana grafer är sällsynta nog att räkna upp. Fosters lista och dess tillägg ger sådana listor. [7] Fosters lista startades på 1930-talet av Ronald Foster under hans tid på Bell Labs , [8] och 1988 (när Foster var 92 [1] ) Fosters lista (en lista över alla symmetriska kubiska grafer upp till 512 hörn, känd vid den tiden) gavs ut som en bok. [9] De första tretton elementen i listan är kubiska symmetriska grafer med upp till 30 hörn [10] [11] (tio av dem är avståndstransitiva ), ges i tabellen nedan
| Toppar | Diameter | Omkrets | Graf | Anteckningar |
|---|---|---|---|---|
| fyra | ett | 3 | komplett graf K 4 | avstånd transitiv, 2-transitiv |
| 6 | 2 | fyra | komplett tvådelad graf K 3,3 | avstånd transitiv, 3-transitiv |
| åtta | 3 | fyra | hörn och kanter på en kub | avstånd transitiv, 2-transitiv |
| tio | 2 | 5 | greve av Petersen | avstånd transitiv, 3-transitiv |
| fjorton | 3 | 6 | Earl av Heawood | avstånd transitiv, 4-transitiv |
| 16 | fyra | 6 | Möbius-Cantor graf | 2-transitiv |
| arton | fyra | 6 | Greve Pappa | avstånd transitiv, 3-transitiv |
| tjugo | 5 | 5 | hörn och kanter på dodekaedern | avstånd transitiv, 2-transitiv |
| tjugo | 5 | 6 | Greve Desargues | avstånd transitiv, 3-transitiv |
| 24 | fyra | 6 | graf över Nauru ( generaliserad Petersen-graf G(12,5)) | 2-transitiv |
| 26 | 5 | 6 | graf F26A [11] | 1-transitiv |
| 28 | fyra | 7 | Earl av Coxeter | avstånd transitiv, 3-transitiv |
| trettio | fyra | åtta | Greve av Thatta-Coxeter | avstånd transitiv, 5-transitiv |
Andra välkända symmetriska kubiska grafer är Dick -grafen , Foster-grafen och Biggs-Smith-grafen . Tio avståndstransitiva grafer listas ovan. Tillsammans med Foster -grafen och Biggs-Smith-grafen är dessa de enda avståndstransitiva graferna.
Icke-kubiska symmetriska grafer inkluderar cykler (grader av 2), kompletta grafer (grader av 4 och högre med 5 eller fler hörn), hyperkubgrafer (grader av 4 och högre med 16 eller fler hörn), och grafer som bildas av hörn och kanterna på oktaedern , icosahedron , cuboctahedron och icosidodecahedron . Rado-grafen ger ett exempel på en symmetrisk graf med ett oändligt antal hörn och en oändlig grad.
Spetsanslutningen för en symmetrisk graf är alltid lika med graden d . [3] Däremot, för allmänna vertextransitiva grafer, begränsas vertexanslutningen nedan av 2( d +1)/3. [2]
En t -transitiv graf av grad 3 eller högre har en omkrets på minst 2( t -1). Det finns dock inga finita t -transitiva grafer av grad 3 eller högre för t ≥ 8. I fallet med grad tre (kubiska symmetriska grafer) finns det inga grafer för t ≥ 6.