Petersenov graf je (kubični) simetrični graf. Vsak par sosednjih točk se lahko preslika v drugega z avtomorfizmom, ker se lahko vsak obroč s petimi točkami preslika v drugega.
Simetrični graf (ali ločnoprehodni graf) G je v teoriji grafovgraf pri katerem za dana dva para sosednjih točku1—v1 in u2—v2 obstaja takšen avtomorfizem:
Graf je simetričen, če njegova grupa avtomorfizmov deluje prehodno nad urejenimi pari sosednjih točk – nad povezavami kot, če bi imele smer).[2] Takšen graf se včasih imenuje tudi 1-ločnoprehodni graf[2] ali zastavnoprehodni graf.[3]
Po definiciji, kjer se ne upošteva u1 in u2, mora biti simetrični graf brez izoliranih točk tudi točkovnoprehoden.[1] Ker zgornja definicija preslikuje eno povezavo v drugo, mor simetrični graf biti tudi povezavnoprehoden. Vendar točkovnoprehoden graf ni nujno simetričen, saj se lahko a—b preslika v c—d, ne pa v d—c. Polsimetrični grafi so na primer povezavnoprehodni in regularni, niso pa točkovnoprehodni.
Vsak povezani simetrični graf mora biti tako točkovno kot tudi povezavnoprehoden. Obratno tudi velja za grafe z liho stopnjo.[3] Vendar za vsako stopnjo obstaja povezani graf, ki je točkovno in povezavno prehoden, ni pa simetričen.[4] Takšni grafi se imenujejo polprehodni grafi.[5] Najmanjši povezani polprehodni graf je Holtov graf s stopnjo 4 in 27-imi točkami.[1][6] Nekateri avtorji rabijo izraz »simetrični graf« za grafe, ki so točkovno in povezavnoprehodni in ne ločnoprehodni. Takšna definicija bi vključevala polprehodne grafe, ki jih zgornja definicija izključuje.
V razdaljnoprehodnem grafu se namesto urejenih parov sosednjih točk (točki, ki sta narazen za razdaljo 1) v definiciji rabita dva para točk, ki sta narazen za enako razdaljo. Takšni grafi so avtomatično simetrični po definiciji.[1]
t-lok je zaporedje takšnih t+1 točk, da sta dve zaporedni točki v zaporedju sosednji in s ponovljenimi točkami narazen za več kot 2 koraka. t-prehodni graf je graf v katerem grupa avtomorfizmov deluje prehodno nad t-loki, ne pa nad (t+1)-loki. Ker so 1-loki preprosto povezave, mora vsak simetrični graf stopnje 3 ali več biti t-prehoden za poljubni t, vrednost t pa se lahko uporabi za nadaljnjo klasifikacijo simetričnih grafov. Kocka je na primer 2-prehodna.[1]
Zgledi
S kombinacijo pogoja simetričnosti in omejitve, da so grafi kubični (vse točke imajo stopnjo 3), se dobi dokaj strog pogoj in takšni grafi so dovolj redki za njihov izpis. Fosterjev popis in njegove razširitve dajo takšne sezname.[7] Fosterjev popis je v 1930-ih začel sestavljati Ronald Martin Foster kot uslužbenec Bellovih laboratorijev[8]. Leta 1988 (ko je bil Foster star 92 let[1]) je bil tedanji popis (z vsemi kubičnimi simetričnimi grafi z do 512 točkami) izdan v knjižni obliki.[9] Prvih trinajst vnosov v seznamu so kubični simetrični grafi z do 30-imi točkami[10][11] (deset od njih je tudi razdaljnoprehodnih (RP); izjeme so naznačene, k-LP – »k-ločnoprehoden«):
Drugi dobro znani kubični simetrični grafi so: Dyckov graf, Fosterjev graf in Biggs-Smithov graf. Deset razdaljnoprehodnih grafov navedenih v razpredelnici skupaj s Fosterjevim grafom in Biggs-Smithovim grafom predstavlja množico edinih kubičnih razdaljnoprehodnih grafov.
Točkovna povezanost simetričnega grafa je vedno enaka stopnji d.[3] Pri točkovnoprehodnih grafih pa je točkovna povezanost omejena z 2(d+1)/3.[2]
t-prehodni graf stopnje 3 ali več ima notranji obseg vsaj 2(t–1). Ne obstajajo pa končni t-prehodni grafi stopnje 3 ali več za t ≥ 8. V primeru stopnje točno enake 3 (kubični simetrični grafi) ni nobenega za t ≥ 6.
Foster, Ronald Martin; Bouwer, Izak Zurk; Chernoff, William W.; Monson, B.; Star, Z. (1988), The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs, ISBN0-919611-19-2
