Симметричный граф

В математической области теории графов граф G $) ,$ является симметричным (или дуготранзитивным если для любых двух пар смежных вершин $u 1 — v 1$ и $u 2 — v 2$ графа $G$ существует автоморфизм

f:V(G)\rightarrow V(G)

такой, что

f(u_{1})=u_{2}

и

f(v_{1})=v_{2}.

^[1]

Другими словами, граф симметричен, если его группа автоморфизмов действует транзитивно на упорядоченных парах соседних вершин (то есть на ребрах, которые считаются имеющими направление). ^[2] Такой граф иногда еще называют 1-дуговым -транзитивным. ^[2] или транзитивный по флагу . ^[3]

По определению (игнорируя $и также$ u2 $) u1$ , симметричный граф без изолированных вершин должен быть вершинно-транзитивным . ^[1] Поскольку приведенное выше определение отображает одно ребро в другое, симметричный граф также должен быть транзитивным по ребрам . Однако реберно-транзитивный граф не обязательно должен быть симметричным, поскольку $a-b$ может отображаться в $c-d$ , но не в $d-c$ . Звездчатые графы являются простым примером того, что они транзитивны по ребрам, но не являются транзитивными по вершинам или симметричными. Еще один пример: полусимметричные графы транзитивны по ребрам и регулярны , но не транзитивны по вершинам.

Таким образом, каждый связный симметричный граф должен быть как вершинно-транзитивным, так и реберно-транзитивным, и обратное верно для графов нечетной степени. ^[3] Однако для четной степени существуют связные графы, которые являются вершинно-транзитивными и реберно-транзитивными, но не симметричными. ^[4] Такие графы называются полутранзитивными . ^[5] Наименьшим связным полутранзитивным графом является граф Холта со степенью 4 и 27 вершинами. ^[1]^[6] Как ни странно, некоторые авторы используют термин «симметричный граф» для обозначения графа, который является транзитивным по вершинам и ребрам, а не к транзитивным по дугам графам. Такое определение будет включать полутранзитивные графы, которые исключены из приведенного выше определения.

Дистанционно -транзитивный граф — это граф, в котором вместо рассмотрения пар соседних вершин (т. е. вершин, находящихся на расстоянии 1 друг от друга), определение охватывает две пары вершин, каждая из которых находится на одинаковом расстоянии друг от друга. Такие графы автоматически симметричны по определению. ^[1]

T $.$ -дуга определяется как последовательность из $t + 1$ вершин, такая, что любые две последовательные вершины в последовательности являются смежными, а любые повторяющиеся вершины находятся на расстоянии более 2 шагов друг от друга t $-$ транзитивный граф — это граф, в котором группа автоморфизмов действует транзитивно на $t$ -дугах , но не на ( $t +1$ )-дугах . Поскольку 1-дуги — это просто ребра, каждый симметричный граф степени 3 или более должен быть $t$ -транзитивным для некоторого $t$ , и значение $t$ можно использовать для дальнейшей классификации симметричных графов. куб 2-транзитивен . Например, ^[1]

Обратите внимание, что традиционно термин «симметричный граф» не дополняет термин « асимметричный граф », поскольку последний относится к графу, который вообще не имеет нетривиальных симметрий.

Примеры

Два основных семейства симметричных графов для любого числа вершин — это графы циклов (степени 2) и полные графы . Далее симметричные графы образуются вершинами и рёбрами правильных и квазиправильных многогранников: куба , октаэдра , икосаэдра , додекаэдра , кубооктаэдра и икосододекаэдра . Расширение куба до n измерений дает графы гиперкуба (с 2 ^н вершины и степень n). Аналогичным образом расширение октаэдра до n измерений дает графы перекрестных многогранников . Это семейство графов (с 2n вершинами и степенью 2n-2) иногда называют графами для коктейльных вечеринок - они представляют собой полные графы с набором ребер. создание идеального соответствия удалено. Дополнительными семействами симметричных графов с четным числом вершин 2n являются равномерно разделенные полные двудольные графы K _n,n и графы-короны на 2n вершинах. Многие другие симметричные графы можно отнести к циркулянтным графам (но не все).

Граф Радо представляет собой пример симметричного графа с бесконечным числом вершин и бесконечной степенью.

Кубические симметричные графы

Сочетание условия симметрии с ограничением на кубичность графов (т. е. все вершины имеют степень 3) дает довольно сильное условие, и такие графы достаточно редки, чтобы их можно было перечислить. Все они имеют четное количество вершин. Перепись Фостера и ее дополнения предоставляют такие списки. ^[7] Перепись Фостера была начата в 1930-х годах Рональдом М. Фостером, когда он работал в Bell Labs . ^[8] а в 1988 году (когда Фостеру было 92 года) ^[1]) текущая на тот момент перепись Фостера (с перечислением всех кубических симметричных графов до 512 вершин) была опубликована в виде книги. ^[9] Первые тринадцать элементов списка представляют собой кубически-симметричные графы с числом вершин до 30. ^[10]^[11] (десять из них также являются дистанционно-транзитивными ; исключения указаны так:

Вершины	Диаметр	Обхват	График	Примечания
4	1	3	Полный граф K ₄	дистанционно-переходной, 2-дуговой переходный
6	2	4	Полный двудольный граф K _3,3	дистанционно-переходной, 3-дуговой переходный
8	3	4	Вершины и ребра куба	дистанционно-переходной, 2-дуговой переходный
10	2	5	Петерсена График	дистанционно-переходной, 3-дуговой переходный
14	3	6	Граф Хивуда	дистанционно-переходный, 4-дуговой переходный
16	4	6	Граф Мёбиуса – Кантора	2-дуговой переходный
18	4	6	Граф Паппуса	дистанционно-переходной, 3-дуговой переходный
20	5	5	Вершины и ребра додекаэдра	дистанционно-переходной, 2-дуговой переходный
20	5	6	Граф Дезарга	дистанционно-переходной, 3-дуговой переходный
24	4	6	Граф Науру ( обобщенный граф Петерсена G(12,5))	2-дуговой переходный
26	5	6	График F26A ^[11]	1-дуга-переходный
28	4	7	Граф Кокстера	дистанционно-переходной, 3-дуговой переходный
30	4	8	Граф Тутта – Кокстера	дистанционно-переходный, 5-дуговой переходный

Другими хорошо известными кубическими симметричными графами являются граф Дика , граф Фостера и граф Биггса-Смита . Перечисленные выше десять дистанционно-транзитивных графов вместе с графом Фостера и графом Биггса-Смита являются единственными кубическими дистанционно-транзитивными графами.

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

Вершинная связность симметричного графа всегда равна степени d . ^[3] Напротив, для вершинно-транзитивных графов в целом связность вершин ограничена снизу величиной 2( d + 1)/3. ^[2]

-транзитивный граф t степени 3 и выше имеет обхват не менее 2( t – 1). Однако не существует конечных t -транзитивных графов степени 3 или более для t ≥ 8. В случае, когда степень равна ровно 3 (кубические симметричные графы), их нет для t ≥ 6.

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. стр. 118–140. ISBN 0-521-45897-8 .
^ Jump up to: ^а ^б ^с Годсил, Крис ; Ройл, Гордон (2001). Алгебраическая теория графов . Нью-Йорк: Спрингер. п. 59 . ISBN 0-387-95220-9 .
^ Jump up to: ^а ^б ^с Бабай, Л (1996). «Группы автоморфизмов, изоморфизм, реконструкция» (PDF) . В Грэме, Р.; Гретшель, М ; Ловас, Л. (ред.). Справочник по комбинаторике . Эльзевир.
^ Бауэр, З. (1970). «Вершинные и реберные транзитивные, но не 1-транзитивные графы» . Канада. Математика. Бык. 13 : 231–237. дои : 10.4153/CMB-1970-047-8 .
^ Гросс, Дж. Л. и Йеллен, Дж. (2004). Справочник по теории графов . ЦРК Пресс. п. 491. ИСБН 1-58488-090-2 .
^ Холт, Дерек Ф. (1981). «Граф, транзитивный по ребрам, но не транзитивный по дугам». Журнал теории графов . 5 (2): 201–204. дои : 10.1002/jgt.3190050210 . .
^ Марстон Кондер , Трехвалентные симметричные графы с числом вершин до 768 , Дж. Комбин. Математика. Комбинировать. Компьютер, том. 20, стр. 41–63.
^ Фостер, Р.М. «Геометрические схемы электрических сетей». Труды Американского института инженеров-электриков 51 , 309–317, 1932.
^ «Перепись Фостера: перепись Р. М. Фостера связанных симметричных трехвалентных графов», Рональд М. Фостер, И. З. Бауэр, В. В. Чернофф, Б. Монсон и З. Стар (1988) ISBN 0-919611-19-2
^ Биггс, с. 148
^ Jump up to: ^а ^б Вайсштейн, Эрик В., « Кубический симметричный граф », из Wolfram MathWorld.

Внешние ссылки

Кубические симметричные графы (Перепись Фостера) . Файлы данных для всех кубических симметричных графов до 768 вершин и некоторых кубических графов до 1000 вершин. Гордон Ройл, обновлено в феврале 2001 г., получено 18 апреля 2009 г.
Трехвалентные (кубические) симметричные графы с числом вершин до 10000 . Марстон Кондер , 2011.

[biggs-1] Jump up to: ^а ^б ^с ^д ^и ^ж Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Кембридж: Издательство Кембриджского университета. стр. 118–140. ISBN 0-521-45897-8 .

[godsil-2] Jump up to: ^а ^б ^с Годсил, Крис ; Ройл, Гордон (2001). Алгебраическая теория графов . Нью-Йорк: Спрингер. п. 59 . ISBN 0-387-95220-9 .

[babai-3] Jump up to: ^а ^б ^с Бабай, Л (1996). «Группы автоморфизмов, изоморфизм, реконструкция» (PDF) . В Грэме, Р.; Гретшель, М ; Ловас, Л. (ред.). Справочник по комбинаторике . Эльзевир.

[4] Бауэр, З. (1970). «Вершинные и реберные транзитивные, но не 1-транзитивные графы» . Канада. Математика. Бык. 13 : 231–237. дои : 10.4153/CMB-1970-047-8 .

[handbook-5] Гросс, Дж. Л. и Йеллен, Дж. (2004). Справочник по теории графов . ЦРК Пресс. п. 491. ИСБН 1-58488-090-2 .

[6] Холт, Дерек Ф. (1981). «Граф, транзитивный по ребрам, но не транзитивный по дугам». Журнал теории графов . 5 (2): 201–204. дои : 10.1002/jgt.3190050210 . .

[7] Марстон Кондер , Трехвалентные симметричные графы с числом вершин до 768 , Дж. Комбин. Математика. Комбинировать. Компьютер, том. 20, стр. 41–63.

[8] Фостер, Р.М. «Геометрические схемы электрических сетей». Труды Американского института инженеров-электриков 51 , 309–317, 1932.

[9] «Перепись Фостера: перепись Р. М. Фостера связанных симметричных трехвалентных графов», Рональд М. Фостер, И. З. Бауэр, В. В. Чернофф, Б. Монсон и З. Стар (1988) ISBN 0-919611-19-2

[10] Биггс, с. 148

[F26A-11] Jump up to: ^а ^б Вайсштейн, Эрик В., « Кубический симметричный граф », из Wolfram MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

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