Symmetrinen graafi (tai kaarien suhteen transitiivinen graafi ) on graafi G , jossa mille tahansa kahdelle vierekkäisten kärkien parille, joiden u 1 - v 1 ja u 2 - v 2 on automorfismi :
f : V ( G ) → V ( G )sellainen että:
f ( u 1 ) = u 2 ja f ( v 1 ) = v 2 . [yksi]Toisin sanoen graafi on symmetrinen, jos sen automorfismiryhmä toimii transitiivisesti järjestetyissä vierekkäisten kärkien pareissa (siis kaikilla reunoilla ikään kuin niillä olisi orientaatio). [2] Tällaisia kuvaajia kutsutaan joskus myös 1-transitiivisiksi kaarien suhteen [2] tai lipputransitiivisiksi . [3]
Määritelmän mukaan symmetristen graafien, joissa ei ole eristettyjä kärkipisteitä, on myös oltava vertex-transitiivisia . [1] Koska edellä olevan määritelmän mukaan reunat voidaan kääntää toisesta toiseen, symmetristen graafien on myös oltava reunatransitiivisia . Reunatransitiivinen graafi ei kuitenkaan välttämättä ole symmetrinen, koska a - b voidaan kuvata c - d : hen , mutta ei d - c . Esimerkiksi puolisymmetriset graafit ovat reunatransitiivisia ja säännöllisiä , mutta eivät kärkitransitiivisia.
Minkä tahansa yhdistetyn symmetrisen graafin on oltava sekä kärkitransitiivinen että reunatransitiivinen, ja päinvastoin pätee parittoman asteen graafisiin. [3] Parillisille asteille on kuitenkin olemassa yhdistettyjä graafia, jotka ovat sekä kärkitransitiivisia että reunatransitiivisia, mutta eivät symmetrisiä. [4] Tällaisia kaavioita kutsutaan puolitransitiivisiksi . [5] Pienin yhdistetty puolitransitiivinen graafi on Holt-graafi , jolla on aste 4 ja 27 kärkeä. [1] [6] Hämmentävästi jotkut kirjoittajat käyttävät termiä "symmetrinen graafi" graafista, joka on sekä kärkitransitiivistä että reunatransitiivistä. Tällainen määritelmä sisältää puolitransitiiviset graafit, jotka on jätetty edellä olevan määritelmän ulkopuolelle.
Etäisyystransitiivinen graafi on graafi, jossa vierekkäiset kärjet ovat samalla kiinteällä etäisyydellä sen sijaan, että ne olisivat yksikköetäisyys. Tällaiset graafit ovat määritelmän mukaan symmetrisiä. [yksi]
T -kaari määritellään t +1 -pisteiden sarjaksi siten, että mitkä tahansa kaksi peräkkäistä kärkeä ovat vierekkäin, ja pisteiden toistoa voi tapahtua aikaisintaan 2 askeleen jälkeen. Graafin sanotaan olevan t -transitiivinen , jos automorfismiryhmä toimii transitiivisesti t -kaareilla, mutta ei ( t +1)-kaareilla. Koska 1-kaaret ovat vain reunoja, minkä tahansa asteen 3 tai enemmän symmetrisen graafin on oltava t -transitiivinen jollekin t :lle, ja t :n arvoa voidaan käyttää graafien luokitteluun. Kuutio on esimerkiksi 2-transitiivinen. [yksi]
Yhdistämällä symmetriaehdot siihen ehtoon, että graafi on kuutio (eli kaikilla pisteillä on aste 3), syntyy riittävän vahva ehto, jotta kaikki tällaiset graafit ovat riittävän harvinaisia luettaviksi. Fosterin lista ja sen laajennukset antavat tällaisia luetteloita. [7] Fosterin listan aloitti 1930-luvulla Ronald Foster ollessaan Bell Labsissa , [8] ja vuonna 1988 (kun Foster oli 92 -vuotias [1] ) Fosterin lista (luettelo kaikista symmetrisistä kuutiograafista 512 kärkeen asti, tuolloin tunnettu) julkaistiin kirjana. [9] Listan ensimmäiset kolmetoista elementtiä ovat kuutiosymmetrisiä graafia, joissa on enintään 30 kärkeä [10] [11] (joista kymmenen ovat etäisyystransitiivisia ), esitetään alla olevassa taulukossa.
| Huiput | Halkaisija | Ympärysmitta | Kaavio | Huomautuksia |
|---|---|---|---|---|
| neljä | yksi | 3 | täydellinen graafi K4 | etäisyys transitiivinen, 2-transitiivinen |
| 6 | 2 | neljä | täydellinen kaksiosainen graafi K 3,3 | etäisyys transitiivinen, 3-transitiivinen |
| kahdeksan | 3 | neljä | kuution kärjet ja reunat | etäisyys transitiivinen, 2-transitiivinen |
| kymmenen | 2 | 5 | Petersenin kreivi | etäisyys transitiivinen, 3-transitiivinen |
| neljätoista | 3 | 6 | Earl of Heawood | etäisyys transitiivinen, 4-transitiivinen |
| 16 | neljä | 6 | Möbius-Cantor-kaavio | 2-transitiivinen |
| kahdeksantoista | neljä | 6 | Kreivi Pappa | etäisyys transitiivinen, 3-transitiivinen |
| kaksikymmentä | 5 | 5 | dodekaedrin kärjet ja reunat | etäisyys transitiivinen, 2-transitiivinen |
| kaksikymmentä | 5 | 6 | Kreivi Desargues | etäisyys transitiivinen, 3-transitiivinen |
| 24 | neljä | 6 | Naurun graafi ( yleistetty Petersenin graafi G(12,5)) | 2-transitiivinen |
| 26 | 5 | 6 | kaavio F26A [11] | 1-transitiivinen |
| 28 | neljä | 7 | Earl of Coxeter | etäisyys transitiivinen, 3-transitiivinen |
| kolmekymmentä | neljä | kahdeksan | Thatta-Coxeterin kreivi | etäisyys transitiivinen, 5-transitiivinen |
Muita tunnettuja symmetrisiä kuutiokaavioita ovat Dick- , Foster- ja Biggs-Smithin graafit . Yllä on listattu kymmenen etäisyyden transitiivista kuvaajaa. Yhdessä Foster- ja Biggs-Smith-kaavion kanssa nämä ovat ainoat etäisyyden transitiiviset kaaviot.
Ei-kuutiosymmetriset graafit sisältävät syklit (asteet 2), täydelliset graafit (asteet 4 ja enemmän 5 tai useammalla kärjellä), hyperkuutiograafit (asteet 4 ja enemmän 16 tai useammalla pisteellä) ja pisteistä ja pisteistä muodostuneet graafit oktaedrin , ikosaedrin , kuuboktaedrin ja ikosidodekaedrin reunat . Rado-graafi antaa esimerkin symmetrisestä graafista, jossa on ääretön määrä pisteitä ja ääretön aste.
Symmetrisen graafin kärkiliitettävyys on aina yhtä suuri kuin aste d . [3] Sitä vastoin yleisten kärkitransitiivisten graafien kohdalla kärkiliitettävyyttä rajoittaa alla 2( d +1)/3. [2]
Asteen 3 tai korkeamman t -transitiivisen graafin ympärysmitta on vähintään 2( t -1). Kuitenkaan ei ole olemassa äärellisiä t -transitiivisia kaavioita, joiden aste on 3 tai korkeampi arvolle t ≥ 8. Asteen tarkalleen kolme (kuutiosymmetriset graafit) tapauksessa t ≥ 6 :lle ei ole kuvaajia .