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

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

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

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

Примеры

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

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

Свойства

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

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

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

Ссылки

• Weisstein, Eric W. Self-Complementary Graph (англ.) на сайте Wolfram MathWorld.