En symmetrisk graf (eller en graf, der er transitiv i forhold til buer ) er en graf G , for et hvilket som helst to par af tilstødende hjørner, hvoraf u 1 - v 1 og u 2 - v 2 er en automorfi :
f : V ( G ) → V ( G )sådan at:
f ( u 1 ) = u 2 og f ( v 1 ) = v 2 . [en]Med andre ord er en graf symmetrisk, hvis dens automorfigruppe virker transitivt på ordnede par af tilstødende hjørner (altså på alle kanter, som om de havde en orientering). [2] Sådanne grafer kaldes nogle gange også 1-transitive med hensyn til buer [2] eller flag-transitive . [3]
Per definition skal symmetriske grafer uden isolerede hjørner også være vertex-transitive . [1] Da kanter ifølge definitionen ovenfor kan oversættes fra den ene til den anden, skal symmetriske grafer også være kanttransitive . En kanttransitiv graf er dog ikke nødvendigvis symmetrisk, da a - b kan afbildes til c - d , men ikke til d - c . Semisymmetriske grafer er f.eks. kanttransitive og regulære , men ikke toppunkttransitive.
Enhver forbundet symmetrisk graf skal være både toppunkttransitiv og kanttransitiv, og det omvendte gælder for grafer med ulige grader. [3] For lige grader er der dog forbundne grafer, der både er toppunkttransitive og kanttransitive, men ikke symmetriske. [4] Sådanne grafer kaldes semi-transitive . [5] Den mindste forbundne semi-transitive graf er Holt-grafen , som har grad 4 og 27 hjørner. [1] [6] Forvirrende nok bruger nogle forfattere udtrykket "symmetrisk graf" for grafer, der både er toppunkttransitive og kanttransitive. En sådan definition omfatter semi-transitive grafer, som er udelukket af definitionen ovenfor.
En afstandstransitiv graf er en graf, hvor i stedet for at være enhedsafstand, er tilstødende hjørner i samme faste afstand. Sådanne grafer er per definition symmetriske. [en]
En t -bue er defineret som en sekvens af t +1-spidser, således at to på hinanden følgende knudepunkter støder op til hinanden, og gentagelse af knudepunkter ikke kan forekomme tidligere end efter 2 trin. En graf siges at være t -transitiv, hvis automorfigruppen virker transitivt på t -buer, men ikke på ( t +1)-buer. Da 1-buer kun er kanter, skal enhver symmetrisk graf af grad 3 eller mere være t -transitiv for nogle t , og værdien af t kan bruges til at klassificere grafer. Terningen er f.eks. 2-transitiv. [en]
Ved at kombinere symmetribetingelserne med betingelsen om, at grafen er kubisk (det vil sige, at alle hjørner har grad 3) genereres en stærk nok betingelse, at alle sådanne grafer er sjældne nok til at opregne. Fosters liste og dens udvidelser giver sådanne lister. [7] Fosters liste blev startet i 1930'erne af Ronald Foster under hans tid på Bell Labs , [8] og i 1988 (da Foster var 92 [1] ) Fosters liste (en liste over alle symmetriske kubiske grafer op til 512 hjørner, kendt på det tidspunkt) blev udgivet som en bog. [9] De første tretten elementer på listen er kubiske symmetriske grafer med op til 30 hjørner [10] [11] (ti af dem er afstandstransitive ), er angivet i tabellen nedenfor
| Toppe | Diameter | Omkreds | Kurve | Noter |
|---|---|---|---|---|
| fire | en | 3 | komplet graf K 4 | afstand transitiv, 2-transitiv |
| 6 | 2 | fire | komplet todelt graf K 3,3 | afstand transitiv, 3-transitiv |
| otte | 3 | fire | hjørner og kanter af en terning | afstand transitiv, 2-transitiv |
| ti | 2 | 5 | greve af Petersen | afstand transitiv, 3-transitiv |
| fjorten | 3 | 6 | jarl af Heawood | afstand transitiv, 4-transitiv |
| 16 | fire | 6 | Möbius-Cantor graf | 2-transitiv |
| atten | fire | 6 | Greve Pappa | afstand transitiv, 3-transitiv |
| tyve | 5 | 5 | spidser og kanter af dodekaederet | afstand transitiv, 2-transitiv |
| tyve | 5 | 6 | Grev Desargues | afstand transitiv, 3-transitiv |
| 24 | fire | 6 | graf af Nauru ( generaliseret Petersen graf G(12,5)) | 2-transitiv |
| 26 | 5 | 6 | graf F26A [11] | 1-transitiv |
| 28 | fire | 7 | Jarl af Coxeter | afstand transitiv, 3-transitiv |
| tredive | fire | otte | Greve af Thatta-Coxeter | afstand transitiv, 5-transitiv |
Andre velkendte symmetriske kubiske grafer er Dick -grafen , Foster-grafen og Biggs-Smith-grafen . Ti afstandstransitive grafer er anført ovenfor. Sammen med Foster -grafen og Biggs-Smith-grafen er disse de eneste afstandstransitive grafer.
Ikke-kubiske symmetriske grafer inkluderer cyklusser (grader på 2), komplette grafer (grader på 4 og derover med 5 eller flere hjørner), hyperkubegrafer (grader på 4 og derover med 16 eller flere hjørner) og grafer dannet af hjørnerne og kanter af oktaeder , icosahedron , cuboctahedron og icosidodecahedron . Rado-grafen giver et eksempel på en symmetrisk graf med et uendeligt antal hjørner og en uendelig grad.
Toppunktforbindelsen af en symmetrisk graf er altid lig med graden d . [3] I modsætning hertil, for generelle vertex-transitive grafer, er toppunktsforbindelsen afgrænset nedenfor af 2( d +1)/3. [2]
En t -transitiv graf af grad 3 eller højere har en omkreds på mindst 2( t -1). Der er dog ingen endelige t -transitive grafer af grad 3 eller højere for t ≥ 8. I tilfælde af grad tre (kubiske symmetriske grafer) er der ingen grafer for t ≥ 6.