Vlastní doplňkový graf - Self-complementary graph

Autokomplementární graf: modrý N je izomorfní s jeho doplňkem, přerušovaná červená Z.

A autokomplementární graf je graf který je izomorfní k jeho doplněk. Nejjednoduššími netriviálními komplementárními grafy jsou 4-vrchol graf cesty a 5-vrchol graf cyklu.

Příklady

Každý Paleyův graf je samo-komplementární.[1] Například 3 × 3 věžní graf (Paleyův graf řádu devět) je komplementární, symetrií, která udržuje středový vrchol na místě, ale vyměňuje si role čtyř bočních středů a čtyř rohů mřížky.[2] Všechno velmi pravidelné autokomplementární grafy s méně než 37 vrcholy jsou Paleyovy grafy; na 37, 41 a 49 vrcholech však existují silně pravidelné grafy, které nejsou grafy Paley.[3]

The Rado graf je nekonečný samokomplementární graf.[4]

Vlastnosti

An n-vertexový komplementární graf má přesně poloviční počet okrajů kompletní graf, tj., n(n - 1) / 4 hrany, a (pokud existuje více než jeden vrchol) musí mít průměr buď 2 nebo 3.[1] Od té doby n(n −1) musí být dělitelné 4, n musí být shodný na 0 nebo 1 mod 4; například 6-vrcholný graf nemůže být doplňkový.

Výpočetní složitost

Problémy s kontrolou, zda jsou dva autokomplementární grafy izomorfní, a s kontrolou, zda je daný graf autokomplementární, jsou ekvivalent polynomiálního času generálovi problém grafového izomorfismu.[5]

Reference

  1. ^ A b Sachs, Horst (1962), „Über selbstkomplementäre Graphen“, Publicationes Mathematicae Debrecen, 9: 270–288, PAN  0151953.
  2. ^ Shpectorov, S. (1998), „Doplňkové l1-grafy ", Diskrétní matematika, 192 (1–3): 323–331, doi:10.1016 / S0012-365X (98) 0007X-1, PAN  1656740.
  3. ^ Rosenberg, I. G. (1982), „Pravidelné a silně pravidelné doplňkové grafy“, Teorie a praxe kombinatoriky, North-Holland Math. Stud., 60, Amsterdam: Severní Holandsko, s. 223–238, PAN  0806985.
  4. ^ Cameron, Peter J. (1997), „Náhodný graf“, Matematika Paula Erdőse, II, Algorithms Combin., 14, Berlín: Springer, s. 333–351, arXiv:1301.7544, Bibcode:2013arXiv1301.7544C, PAN  1425227. Viz zejména návrh 5.
  5. ^ Colbourn, Marlene J .; Colbourn, Charles J. (1978), „Graph isomorphism and self -plementary graphs“, Novinky SIGACT, 10 (1): 25–29, doi:10.1145/1008605.1008608.

externí odkazy