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

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

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

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

Примеры

Любой граф Пэли является самодополнительным^[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]}.