Самодополнительный граф

Самодополнительный граф: голубой граф N изоморфен своему дополнению, красному графу Z.
Самодополнительный граф: голубой граф изоморфен своему дополнению, красному графу.

Самодополнительный граф — это граф, изоморфный своему дополнению. Простейшие нетривиальные самодополнительные графы — это путь, состоящий из 4 вершин и цикл из 5 вершин.

Примеры

Любой граф Пэли является самодополнительным[1]. Например, 3 × 3 ладейный граф (граф Пэли девятого порядка) тоже самодополнителен ввиду симметрии, сохраняющей центральную вершину на месте, но обменивающей роли средних точек по четырём краям и углов решётки[2]. Все сильно регулярные самодополнительные графы с менее чем 37 вершинами являются графами Пэли. Однако существуют строго регулярные графы с 37, 41 и 49 вершинами, не являющиеся графами Пэли[3].

Граф Радо является бесконечным самодополнительным графом.

Свойства

Самодополнительный граф с n вершинами имеет в точности половину числа рёбер полного графа, т. е. n(n − 1)/4 рёбер, и (если вершин больше одной) его диаметр должен быть либо 2, либо 3[1]. Поскольку n(n −1) должно делиться на 4, n должно быть сравнимым с 0 или 1 по модулю 4. Например, граф с 6 вершинами не может быть самодополнительным.

Вычислительная сложность

Задача проверки, являются ли два самодополнительных графа изоморфными и проверка, является ли заданный граф самодополнительным, эквивалентны по времени выполнения[англ.] общей задаче проверки изоморфизма графов[англ.][4].

Примечания

  1. ↑ 1 2 Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. — 1962. — Т. 9. — С. 270—288.
  2. ↑ S. Shpectorov. Complementary l1-graphs // Discrete Mathematics. — 1998. — Т. 192, вып. 1-3. — С. 323—331. — doi:10.1016/S0012-365X(98)0007X-1.
  3. ↑ I. G. Rosenberg. Theory and practice of combinatorics. — 1982. — Т. 60. — С. 223—238.
  4. ↑ Marlene J. Colbourn, Charles J. Colbourn. Graph isomorphism and self-complementary graphs // SIGACT News. — 1978. — Т. 10, вып. 1. — С. 25—29. — doi:10.1145/1008605.1008608.

Ссылки