Вершинно-транзитивный граф - Vertex-transitive graph - Wikipedia

Семейства графов, определяемые их автоморфизмами
дистанционно-транзитивный→дистанционно-регулярный←строго регулярный
↓
симметричный (дуго-транзитивный)←т-переходный, т ≥ 2кососимметричный
↓
(если подключен)
вершинно- и реберно-транзитивные		→реберно-транзитивные и регулярные→ребро-транзитивный
↓↓↓
вершинно-транзитивный→обычный→(если двудольный)
двурегулярный
↑
Граф Кэли←нулевой симметричныйасимметричный

в математический поле теория графов, а вершинно-транзитивный граф это график грамм в котором для любых двух вершин v1 и v2 из грамм, существует некоторое автоморфизм

такой, что

Другими словами, граф является вершинно-транзитивным, если его группа автоморфизмов действует переходно на его вершинах.[1] Граф вершинно-транзитивный если и только если это дополнение к графу есть, поскольку действия группы идентичны.

Каждый симметричный граф без изолированные вершины является вершинно-транзитивным, и каждый вершинно-транзитивный граф является обычный. Однако не все вершинно-транзитивные графы симметричны (например, ребра усеченный тетраэдр ), и не все регулярные графы вершинно-транзитивны (например, Граф Фрухта и График Титце ).

Конечные примеры

Края усеченный тетраэдр образуют вершинно-транзитивный граф (также Граф Кэли ) который не симметричный.

Конечные вершинно-транзитивные графы включают симметричные графы (такой как Граф Петерсена, то График Хивуда а вершины и ребра Платоновы тела ). Конечная Графики Кэли (Такие как кубические циклы ) также вершинно-транзитивны, как и вершины и ребра Архимедовы тела (хотя только два из них симметричны). Поточник, Спига и Верре построили перепись всех связных кубических вершинно-транзитивных графов не более чем с 1280 вершинами.[2]

Хотя каждый граф Кэли является вершинно-транзитивным, существуют другие вершинно-транзитивные графы, которые не являются графами Кэли. Самый известный пример - граф Петерсена, но можно построить и другие, включая линейные графики из ребро-транзитивный не-двудольный графики с странный степени вершины.[3]

Характеристики

В граничное соединение вершинно-транзитивного графа равна степень d, в то время как вершинная связность будет не менее 2 (d + 1)/3.[4]Если степень 4 или меньше, или график также ребро-транзитивный, либо граф является минимальным Граф Кэли, то связность вершин также будет равна d.[5]

Бесконечные примеры

Бесконечные вершинно-транзитивные графы включают:

Два счетный вершинно-транзитивные графы называются квазиизометрический если соотношение их функции расстояния ограничена снизу и сверху. Известный догадка заявил, что каждый бесконечный вершинно-транзитивный граф квазиизометричен Граф Кэли. Контрпример был предложен Diestel и Лидер в 2001.[6] В 2005 году Эскин, Фишер и Уайт подтвердили контрпример.[7]

Смотрите также

Рекомендации

  1. ^ Годсил, Крис; Ройл, Гордон (2001), Алгебраическая теория графов, Тексты для выпускников по математике, 207, Нью-Йорк: Springer-Verlag.
  2. ^ Поточник П., Спига П. и Веррет Г. (2013), "Кубические вершинно-транзитивные графы с числом вершин до 1280", Журнал символических вычислений, 50: 465–477, arXiv:1201.5317, Дои:10.1016 / j.jsc.2012.09.002.
  3. ^ Лаури, Йозеф; Скапеллато, Рафаэле (2003), Темы автоморфизмов и реконструкции графов, Студенческие тексты Лондонского математического общества, 54, Кембридж: Издательство Кембриджского университета, стр. 44, ISBN  0-521-82151-7, МИСТЕР  1971819. Лаури и Скапеллето приписывают эту постройку Марку Уоткинсу.
  4. ^ Годсил, К. и Ройл, Г. (2001), Алгебраическая теория графов, Springer Verlag
  5. ^ Бабай, Л. (1996), Технический отчет TR-94-10, Чикагский университет[1] В архиве 2010-06-11 на Wayback Machine
  6. ^ Дистель, Рейнхард; Лидер, Имре (2001), "Гипотеза о пределе графов не-Кэли" (PDF), Журнал алгебраической комбинаторики, 14 (1): 17–25, Дои:10.1023 / А: 1011257718029.
  7. ^ Эскин, Алекс; Фишер, Дэвид; Уайт, Кевин (2005). «Квазиизометрии и жесткость разрешимых групп». arXiv:math.GR/0511647..

внешняя ссылка