Граф Дика

Перейти к навигации Перейти к поиску

Граф Дика

Вершин	32
Рёбер	48
Радиус	5
Диаметр	5
Обхват	6
Автоморфизмы	192
Хроматическое число	2
Хроматический индекс	3
Свойства	Симметричный кубический гамильтонов двудольный Граф Кэли
Медиафайлы на Викискладе

Граф Дика — 3-регулярный граф с 32 вершинами и 48 рёбрами, назван в честь Вальтера фон Дика^[1]^[2].

Граф является гамильтоновым графом с 120 различными гамильтоновыми циклами. Его хроматическое число равно 2, хроматический индекс равен 3, его радиус равен 5, диаметр равен 5 и обхват равен 6. Он является также 3-вершинно-связным и 3-рёберно-связным.

Граф Дика является тороидальным, и двойственный граф его тороидального вложения — это граф Шрикханде, строго регулярный симметричный гамильтонов граф.

Алгебраические свойства

Группа автоморфизмов графа Дика — это группа порядка 192^[3]. Она действует транзитивно на вершины и рёбра графа. Таким образом, граф Дика является симметричным. Он имеет автоморфизмы, которые переводят любую вершину в любую другую вершину и любое ребро в любое другое ребро. В списке Фостера граф Дика, обозначенный как F32A, является единственным кубическим симметричным графом с 32 вершинами^[4].

Характеристический многочлен графа Дика равен $(x-3)(x-1)^{9}(x+1)^{9}(x+3)(x^{2}-5)^{6}$ .

Карта Дика

Граф Дика является остовом^[англ.] симметричного паркета поверхности третьего рода из двенадцати восьмиугольников, известного как карта Дика или Паркет Дика. Двойственный граф этого паркета является полным трёхдольным графом K_4,4,4^[5]^[6].

Галерея

Альтернативное изображение графа Дика.
Хроматическое число графа Дика равно 2.
Хроматический индекс графа Дика равен 3.

Примечания

↑ W. Dyck. Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen // Math. Ann.. — Т. 17. — doi:10.1007/bf01446929.
↑ Weisstein, Eric W. Dyck Graph (англ.) на сайте Wolfram MathWorld.
↑ Royle, G. F032A data (недоступная ссылка)
↑ M. Conder, P. Dobcsányi. Trivalent symmetric graphs up to 768 vertices // J. Combin. Math. Combin. Comput.. — 2002. — Т. 40. — С. 41–63.
↑ W. Dyck. Notiz über eine reguläre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung // Math. Ann.. — 1880. — Т. 17. — С. 510–516.
↑ A. Ceulemans. The tetrakisoctahedral group of the Dyck graph and its molecular realization. // Molecular physics. — 2004. — Т. 102, вып. 11. — С. 1149-1163. — doi:10.1080/00268970410001728780.

Похожие исследовательские статьи

Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда.

Граф Мёбиуса — Кантора — симметричный двудольный кубический граф с 16 вершинами и 24 рёбрами, названный в честь Августа Фердинанда Мёбиуса и Зелигмана Кантора (1857—1903). Его можно определить как обобщённый граф Петерсена $\text{[math]}$ , то есть он образован вершинами восьмиугольника, соединёнными с восьмиугольной звездой, в которой каждая точка соединена с третьей по счёту точкой.

В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа. Он назван в честь Паппа Александрийского, математика Древней Греции, который верил, что доказал «теорему о шестиугольнике», в которой описывал конфигурацию Паппа. Все кубические дистанционно-регулярные графы известны. Граф Паппа — один из тринадцати таких графов.

Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Греем в 1932 году, затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Фолкманом в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.

Граф Фостера — двудольный 3-регулярный граф с 90 вершинами и 135 рёбрами. Граф Фостера является гамильтоновым, имеет хроматическое число 2, хроматический индекс 3, радиус 8, диаметр 8 и обхват 10. Также является вершинно 3-связным и рёберно 3-связным.

Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году.

Граф Биггса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами. Назван в честь Биггса и Смита, описавших граф в 1971 году.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами. Граф был назван Дэвидом Эпштейном по аналогии с двенадцатилучевой звездой на флаге Науру.

В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

Граф F26A — симметричный двудольный кубический граф с 26 вершинами и 39 рёбрами.

В теории графов граф Харриса или (3-10)-клетка Харриса — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

В теории графов граф Харриса — Вонга — это 3-регулярный неориентированный граф с 70 вершинами и 105 рёбрами.

Граф Хортона — 3-регулярный граф с 96 вершинами и 144 рёбрами, открытый Джозефом Хортоном. Бонди и Мурти опубликовали в 1976 этот граф в качестве контрпримера гипотезе Татта, что любой кубический 3-связный двудольный граф является гамильтоновым.

Граф Фолкмана — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами.

11-клетка Балабана или (3-11)-клетка Балабана — это 3-регулярный граф с 112 вершинами и 168 рёбрами, названные именем румынского химика Александру Т. Балабана.

Граф Холта или граф Дойла является наименьшим полутранзитивным графом, то есть наименьшим примером вершинно-транзитивного и рёберно-транзитивного графа, который не является симметричным. Такие графы не часто встречаются. Граф назван именами Питера Дж. Дойла и Дерека Ф. Холта, обнаружившими граф независимо в 1976 и 1981 соответственно.

Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман и опубликовал в 1963. Граф коспектрален графу гиперкуба Q₄.

Граф Робертсона или (4,5)-клетка — это 4-регулярный неориентированный граф с 19 вершинами и 38 рёбрами, названный именем Нейла Робертсона.

3-регулярный граф Клейна — кубический граф с 56 вершинами и 84 рёбрами; назван по имени Феликса Клейна с двойственным ему 7-регулярным графом.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.