Самодополнительный граф — это граф , изоморфный своему дополнению . Простейшие нетривиальные самодополнительные графы — это путь , состоящий из 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. (англ.) на сайте Wolfram MathWorld .