Bár a legtöbb gráfnak az identitáson kívül nincs más automorfizmusa, igen sok gráf, mely különböző kombinatorikus, geometriai, vagy algebrai struktúrából származik, nagy automorfizmuscsoporttal rendelkezik, sőt sokszor ezzel van karakterizálva. Ez teszi fontossá a gráfok struktúrája és az automorfizmuscsoportjuk közötti viszony tanulmányozását.
A korai időszakban a vizsgálatok egyik főiránya főképp függetlenségi eredményeket tartalmazott: ezek azt allapították meg, hogy a gráfra tett igen erős restrikciók alig adnak megszorítást az automorfizmuscsoportjukra. Ez adott automorfizmuscsoporttal rendelkező gráfok konstrukcióját jelenti, melyre manapság meglehetősen jól kidolgozott módszerek vannak. A másik megközelítés, melyben gráfok olyan tulajdonságait keressük, melyek valóban leszükítik az automorfizmuscsoportjukat, sokkal inkább igényel „ad hoc” módszereket.
Ha az automorfizmuscsoportot nemcsak úgy tekintjük, mint egy absztrakt csoportot, hanem úgy is, mint egy permutációs csoportot, akkor persze szorosabb viszonyt találunk gráfok szerkezetével. Például az a tulajdonság, hogy egy automorfizmuscsoport tranzitív, maga után vonja a gráf sok érdekes tulajdonságát.
Ha az automorfizmuscsoport helyett az endomorfizmus-félcsoportot tesszük vizsgálataink tárgyává, hasonló eredményeket kapunk, komplikáltabb konstrukciókkal. Találunk azonban egészen meglepő új jelenségeket is (lásd az utolsó feladatot).
Mi az automorfizmuscsoportja a Petersen gráfnak (9. ábra, 11.2 gyakorlat)?
(a) Mutassuk meg hogy a dodekaéder
automorfizmuscsoportja (11. ábra) izomorf
(b) A kocka automorfizmuscsoportja izomorf
Konstruáljunk egy gráfot, melynek
automorfizmuscsoportja izomorf
Legyen
Adott véges
Legyen
(a) Bármely turnamentnek páratlan sok automorfizmusa van.
(b)* Minden
Adott egy véges
Ha
Legyen
Legyen
(a) Legyen
(b) Legyen
* * * |
(a) Ha egy
(b) Konstruáljunk olyan gráfot, melynek
automorfizmuscsoportja tranzitív és izomorf
(c)* Konstruáljunk egy egyszerű gráfot ezzel a
tulajdonsággal, elég nagy
Az
(a) Legyen
(b) Milyen nagy kell, hogy legyen egy
(c) Egy egyszerű, összefüggő gráf, melynek él-tranzitív az
automorfizmuscsoportja és melyben minden pont foka legalább
Ha egy összefüggő, páros sok pontból álló
A
Mely síkgráfoknak van él-tranzitív automorfizmus csoportjuk?
Tegyük fel, hogy egy
(a) Tegyük fel, hogy
(b) Tegyük fel, hogy
(c) Legyen
Legyen
* * * |
Határozzuk meg a Petersen gráf endomorfizmusait (9. ábra, 11.2 gyakorlat).
Konstruáljunk merev gráfot.
(a) Legyen
(b) Bizonyítsuk be, hogy létezik ilyen egyszerű gráf is.
(a) Ha
(b)* Tetszőleges