Symetrický graf (neboli graf tranzitivní vzhledem k obloukům ) je graf G , pro libovolné dva páry sousedních vrcholů, z nichž u 1 - v 1 a u 2 - v 2 existuje automorfismus :
f : V ( G ) → V ( G )takové, že:
f ( u1 ) = u2 a f ( v1 ) = v2 . _ _ [jeden]Jinými slovy, graf je symetrický, pokud jeho skupina automorfismu působí tranzitivně na uspořádané dvojice sousedních vrcholů (tedy na všech hranách, jako by měly orientaci). [2] Takové grafy se někdy také nazývají 1-tranzitivní s ohledem na oblouky [2] nebo flag-transitive . [3]
Podle definice musí být symetrické grafy bez izolovaných vrcholů také vertex-tranzitivní . [1] Vzhledem k tomu, že podle výše uvedené definice mohou být hrany překládány z jedné na druhou, symetrické grafy musí být také hraně tranzitivní . Hraně-tranzitivní graf však nemusí být nutně symetrický, protože a - b lze zobrazit na c - d , ale ne na d - c . Například semisymetrické grafy jsou hraně tranzitivní a pravidelné , ale ne vertexově tranzitivní.
Jakýkoli připojený symetrický graf musí být jak vertex-tranzitivní, tak hranově-tranzitivní, a obráceně to platí pro grafy lichého stupně. [3] Pro sudé stupně však existují spojené grafy, které jsou jak vertex-tranzitivní, tak hranově-tranzitivní, ale nejsou symetrické. [4] Takové grafy se nazývají semi-tranzitivní . [5] Nejmenší souvislý semi-tranzitivní graf je Holtův graf , který má 4. stupeň a 27 vrcholů. [1] [6] Je matoucí, že někteří autoři používají termín "symetrický graf" pro grafy, které jsou jak vertex-tranzitivní, tak hranově-tranzitivní. Taková definice zahrnuje semi-tranzitivní grafy, které výše uvedená definice vylučuje.
Vzdálenost-tranzitivní graf je graf, ve kterém jsou sousední vrcholy místo jednotkové vzdálenosti ve stejné pevné vzdálenosti. Takové grafy jsou podle definice symetrické. [jeden]
Oblouk t je definován jako posloupnost t +1 vrcholů tak, že libovolné dva po sobě jdoucí vrcholy sousedí a k opakování vrcholů může dojít nejdříve po 2 krocích. O grafu se říká , že je t -tranzitivní, jestliže skupina automorfismu působí tranzitivně na t -obloucích , ale ne na ( t +1) -obloucích. Protože 1-oblouky jsou jen hrany, každý symetrický graf stupně 3 nebo více musí být t - tranzitivní pro nějaké t a hodnotu t lze použít ke klasifikaci grafů. Kostka je například 2-tranzitivní. [jeden]
Kombinace podmínek symetrie s podmínkou, že graf je kubický (to znamená, že všechny vrcholy mají stupeň 3) generuje dostatečně silnou podmínku, že všechny takové grafy jsou dostatečně vzácné na to, aby je bylo možné vyčíslit. Fosterův seznam a jeho rozšíření takové seznamy poskytují. [7] Fosterův seznam založil ve 30. letech Ronald Foster během svého působení v Bell Labs [ 8] a v roce 1988 (kdy bylo Fosterovi 92 [1] ) Fosterův seznam (seznam všech symetrických kubických grafů až do 512 vrcholů, známý v té době) byl vydán jako kniha. [9] Prvních třináct prvků seznamu jsou kubické symetrické grafy s až 30 vrcholy [10] [11] (deset z nich je vzdálenostně tranzitivních ), jsou uvedeny v tabulce níže
| Vrcholy | Průměr | obvod | Graf | Poznámky |
|---|---|---|---|---|
| čtyři | jeden | 3 | kompletní graf K 4 | vzdálenost tranzitivní, 2-tranzitivní |
| 6 | 2 | čtyři | kompletní bipartitní graf K 3,3 | vzdálenost tranzitivní, 3-tranzitivní |
| osm | 3 | čtyři | vrcholy a hrany krychle | vzdálenost tranzitivní, 2-tranzitivní |
| deset | 2 | 5 | hrabě z Petersenu | vzdálenost tranzitivní, 3-tranzitivní |
| čtrnáct | 3 | 6 | hrabě z Heawood | vzdálenost tranzitivní, 4-tranzitivní |
| 16 | čtyři | 6 | Möbiův-Cantorův graf | 2-tranzitivní |
| osmnáct | čtyři | 6 | hrabě Pappa | vzdálenost tranzitivní, 3-tranzitivní |
| dvacet | 5 | 5 | vrcholy a hrany dvanáctistěnu | vzdálenost tranzitivní, 2-tranzitivní |
| dvacet | 5 | 6 | hrabě Desargues | vzdálenost tranzitivní, 3-tranzitivní |
| 24 | čtyři | 6 | graf Nauru ( zobecněný Petersenův graf G(12,5)) | 2-tranzitivní |
| 26 | 5 | 6 | graf F26A [11] | 1-tranzitivní |
| 28 | čtyři | 7 | hrabě z Coxeter | vzdálenost tranzitivní, 3-tranzitivní |
| třicet | čtyři | osm | Hrabě z Thatta-Coxeter | vzdálenost tranzitivní, 5-tranzitivní |
Dalšími známými symetrickými kubickými grafy jsou Dickův graf , Fosterův graf a Biggs-Smithův graf . Výše je uvedeno deset grafů přechodu na vzdálenost. Spolu s Fosterovým grafem a Biggs-Smithovým grafem jsou to jediné grafy s přechodem na vzdálenost.
Nekubické symetrické grafy zahrnují cykly (stupně 2), úplné grafy (stupně 4 a vyšší s 5 nebo více vrcholy), grafy hyperkrychle (stupně 4 a vyšší s 16 nebo více vrcholy) a grafy tvořené vrcholy a okraje osmistěnu , dvacetistěnu , kuboktaedru a dvacetistěnu . Rado graf uvádí příklad symetrického grafu s nekonečným počtem vrcholů a nekonečným stupněm.
Vrcholová konektivita symetrického grafu je vždy rovna stupni d . [3] Naproti tomu u obecných vertex-tranzitivních grafů je vrcholová konektivita níže omezena 2( d +1)/3. [2]
t - tranzitivní graf stupně 3 nebo vyššího má obvod alespoň 2( t - 1). Neexistují však žádné konečné t -tranzitivní grafy stupně 3 nebo vyšší pro t ≥ 8. V případě stupně přesně tři (kubické symetrické grafy) neexistují žádné grafy pro t ≥ 6.