Самодоповняльний граф — це граф, ізоморфний своєму доповненню. Найпростіші нетривіальні самодоповняльні графи — це шлях, що складається з 4 вершин і цикл з 5 вершин.
Приклади Будь-який граф Пелі є самодоповняльним. Наприклад, 3 × 3 туровий граф (граф Пелі 9-го порядку) теж самодоповняльний, зважаючи на симетрію, що зберігає центральну вершину на місці, але обмінює ролі середніх точок по чотирьох краях і кутів ґратки. Всі сильно регулярні самодоповняльні графи з менш ніж 37 вершинами є графами Пелі. Однак існують строго регулярні графи з 37, 41 і 49 вершинами, які не є графами Пелі.
Граф Радо є нескінченним самодоповняльним графом.
Властивості Самодоповняльний граф з n вершинами має рівно половину числа ребер повного графа, тобто n(n − 1)/4 ребер, і (якщо вершин більше однієї) його діаметр має бути або 2, або 3. Оскільки n(n -1) має ділитися на 4, n має бути порівнянним з 0 або 1 за модулем 4. Наприклад, граф з 6 вершинами не може бути самодоповняльним.
Обчислювальна складність Задача перевірки, чи є два самодоповняльних графм ізоморфними і перевірка, чи є заданий граф самодоповняльним, еквівалентні за часом виконання загальній .
Примітки
Посилання