Самодополняющий граф
В математической области теории графов — самодополняющий граф это граф , который изоморфен своему дополнению . Простейшими нетривиальными самодополняющими графами являются с 4 вершинами граф путей и с 5 вершинами граф циклов . Не существует известной характеристики самодополняющих графов.
Примеры [ править ]
Каждый граф Пэли самодополнителен. [1] Например, ладейный граф 3 × 3 (граф Пэли девятого порядка) является самодополняющим благодаря симметрии, которая сохраняет центральную вершину на месте, но меняет роли четырех боковых середин и четырех углов сетки. [2] Все сильно регулярные самодополняющие графы с числом вершин менее 37 являются графами Пэли; однако существуют сильно регулярные графы с 37, 41 и 49 вершинами, которые не являются графами Пэли. [3]
Граф Радо — это бесконечный самодополняющий граф. [4]
Свойства [ править ]
полный граф , Самодополняющий граф с n -вершинами имеет ровно вдвое меньше ребер, чем т . е. n ( n - 1)/4 ребра, и (если вершин больше одной) он должен иметь диаметр либо 2, либо 3. [1] Поскольку n ( n - 1) должно делиться на 4, n должно быть конгруэнтно 0 или 1 по модулю 4; например, граф с 6 вершинами не может быть самодополняющим.
Вычислительная сложность [ править ]
Проблемы проверки изоморфности двух самодополняющих графов и проверки того, является ли данный граф самодополняющим, полиномиально эквивалентны общей проблеме изоморфизма графов . [5]
Ссылки [ править ]
- ^ Перейти обратно: а б Сакс, Хорст (1962), «Über selbstkoplementäre Graphen», Mathematical Publications Debrecen , 9 : 270–288, MR 0151953 .
- ^ Шпекторов С. (1998), «Дополнительные l 1 -графы», Дискретная математика , 192 (1–3): 323–331, doi : 10.1016/S0012-365X(98)0007X-1 , MR 1656740 .
- ^ Розенберг, И.Г. (1982), «Регулярные и сильно регулярные самодополняющие графы», Теория и практика комбинаторики , North-Holland Math. Студ., вып. 60, Амстердам: Северная Голландия, стр. 223–238, MR 0806985 .
- ^ Кэмерон, Питер Дж. (1997), «Случайный граф», Математика Пола Эрдеша, II , Комбинация алгоритмов, том. 14, Берлин: Springer, стр. 333–351, arXiv : 1301.7544 , Bibcode : 2013arXiv1301.7544C , MR 1425227 . См., в частности, предложение 5.
- ^ Колборн, Марлен Дж.; Колборн, Чарльз Дж. (1978), «Изоморфизм графов и самодополняющие графы», SIGACT News , 10 (1): 25–29, doi : 10.1145/1008605.1008608 .