V teorii grafů je oběžný graf neorientovaný graf , který má cyklickou skupinu symetrie , která zahrnuje symetrii, která přenese jakýkoli vrchol do jakéhokoli jiného vrcholu .
Kruhové grafy lze definovat několika ekvivalentními způsoby [1] :
Jakýkoli cyklus je obíhajícím grafem, stejně jako jakákoli koruna .
Paleyovy grafy řádu (kde je prvočíslo shodné s 1 modulo 4) jsou grafy, ve kterých jsou vrcholy čísla od 0 do n − 1 a dva vrcholy sousedí, pokud je rozdíl odpovídajících čísel kvadratický zbytek modulo . Vzhledem k tomu, že přítomnost nebo nepřítomnost hrany závisí pouze na rozdílu v číslech modulo vertexů , je každý Paleyův graf obíhajícím grafem.
Jakýkoli Möbiův žebřík je obíhajícím grafem, stejně jako jakýkoli úplný graf . Kompletní bipartitní graf je oběžný, pokud mají obě části stejný počet vrcholů.
Jestliže dvě čísla a jsou coprime , pak m × n věžový graf (graf, který má vrchol v každé buňce šachovnice m × n a hranu mezi libovolnými dvěma buňkami, pokud se věž může přesunout z jedné buňky do druhé jedním tahem ) je cirkulující graf. Je to důsledek toho, že jeho symetrie obsahují jako podgrupu cyklickou grupu {{{1}}} . Zobecněním tohoto případu je, že přímý součin grafů mezi libovolnými obíhajícími grafy s vrcholy a vede k oběžnému grafu [1] .
Mnoho ze známých dolních hranic pro Ramseyho čísla pochází z příkladů cirkulujících grafů s malými maximálními klikami a malými maximálními nezávislými množinami [2] .
Cirkulující graf (nebo , nebo ) se skoky je definován jako graf s očíslovanými uzly a každý uzel sousedí s 2 k uzlům modulo .
Samokomplementární graf je graf, ve kterém odstranění existujících hran a přidání chybějících vede ke grafu isomorfnímu k původnímu.
Například cyklický graf s pěti vrcholy se samodoplňuje a je také oběhový. Obecněji platí, že jakýkoli Paleyův graf je samokomplementárním cirkulujícím grafem [3] . Horst Sachs ukázal, že má-li číslo tu vlastnost, že jakýkoli prvočísel je shodný s 1 modulo 4, pak existuje samokomplementární cirkulující graf s vrcholy. Předpokládal, že tato podmínka je nezbytná, to znamená, že pro jiné hodnoty neexistují samokomplementární cirkulační grafy [1] [3] . Dohad byl prokázán o 40 let později Wilfredem [1] .
Oběžné číslování oběžného grafu definujeme jako označení vrcholů grafu čísly od 0 do n − 1 tak, že pokud dva vrcholy a sousedí, pak libovolné dva vrcholy s čísly a ( z − x + y ) mod n jsou také sousedící. Ekvivalentně je oběžné číslování vertexové číslování, takže matice sousednosti grafu je oběžná matice.
Nechť je celé číslo coprime c , a nechť je libovolné celé číslo. Poté lineární funkce ax + b transformuje číslování oběžníků na jiné číslování oběžníků. András Ádám se domníval, že lineární zobrazení je jediný způsob, jak přečíslovat vrcholy grafu, který zachovává vlastnost oběhovosti. To znamená, že pokud a jsou dva izomorfní oběžné grafy s různým číslováním, pak existuje lineární transformace, která transformuje číslování pro na číslování pro . Jak se však ukázalo, Adamova hypotéza není správná. Jako protipříklad slouží grafy se 16 vrcholy; vertex in je spojen se šesti sousedy x ± 1 , x ± 2 a x ± 7 (mod 16), zatímco v šesti sousedech jsou x ± 2 , x ± 3 a x ± 5 (mod 16) . Tyto dva grafy jsou izomorfní, ale jejich izomorfismus nelze získat lineární transformací. [jeden]