Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Самодополняющий граф: синий N изоморфен своему дополнению, красный пунктир Z.

Самодополнительный граф является графиком , который является изоморфно его дополнением . Простейшие нетривиальные самодополняемые графы - это 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]

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. «Самодополняемый граф» . MathWorld .