Самодополнительный граф является графиком , который является изоморфно его дополнением . Простейшие нетривиальные самодополняемые графы - это 4-вершинный граф путей и 5-вершинный циклический граф .
Примеры [ править ]
Каждый граф Пэли самодополняемый. [1] Например, граф ладьи 3 × 3 (граф Пэли девятого порядка) самодополняется благодаря симметрии, которая удерживает центральную вершину на месте, но меняет роли четырех боковых средних точек и четырех углов сетки. . [2] Все сильно регулярные самодополняемые графы с числом вершин менее 37 являются графами Пэли; однако есть сильно регулярные графы с 37, 41 и 49 вершинами, которые не являются графами Пэли. [3]
Граф Rado - это бесконечный самодополняющий граф. [4]
Свойства [ править ]
П -vertex самодополнительный граф имеет ровно половину числа краев полного графа , то есть п ( п - 1) / 4 ребра, и (если имеется более одной вершины) оно должно иметь диаметр 2 или 3. [1] Поскольку n ( n −1) должно делиться на 4, n должно быть конгруэнтно 0 или 1 по модулю 4; например, граф с 6 вершинами не может быть самодополняющим.
Вычислительная сложность [ править ]
Проблемы проверки того, являются ли два самодополняющих графа изоморфными, и проверки того, является ли данный граф самодополняющим, эквивалентны с полиномиальным временем общей проблеме изоморфизма графов . [5]
Ссылки [ править ]
- ^ a b Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Publicationes Mathematicae Debrecen , 9 : 270–288, MR 0151953.
- ^ Shpectorov, С. (1998), "комплементарный л 1 -графы", дискретная математика , 192 (1-3): 323-331, DOI : 10.1016 / S0012-365X (98) 0007X-1 , МР 1656740 .
- ^ Розенберг, И.Г. (1982), "Регулярные и сильно регулярные самодополняемые графы", Теория и практика комбинаторики , North-Holland Math. Stud., 60 , Амстердам: Северная Голландия, стр. 223–238, MR 0806985 .
- ^ Кэмерон, Питер Дж. (1997), "Случайный граф", Математика Пола Эрдеша, II , Объединение алгоритмов, 14 , Берлин: Springer, стр. 333–351, arXiv : 1301.7544 , Bibcode : 2013arXiv1301.7544C , MR 1425227 . См., В частности, предложение 5.
- ^ Colbourn, Marlene J .; Colbourn, Charles J. (1978), "изоморфизм графов и самодополнительных графов", SIGACT News , 10 (1): 25-29, DOI : 10,1145 / 1008605,1008608.
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. «Самодополняемый граф» . MathWorld .