7-регулярный граф Клейна

7-регулярный граф Клейна

Назван в честь	Феликс Кляйн
Вершин	24
Рёбер	84
Радиус	3
Диаметр	3
Обхват	3
Автоморфизмы	336
Хроматическое число	4
Хроматический индекс	7
Свойства	симметричный гамильтонов вершинно 3-связный рёберно 3-связный

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

Граф гамильтонов, имеет хроматическое число 4, хроматический индекс 7, радиус 3, диаметр 3 и обхват 3. Граф, как и двойственный ему 3-регулярный, можно вложить в ориентируемую поверхность рода 3, на которой он образует граф с 56 треугольными областями, двойственный карте Клейна; символ Шлефли — {3,7}₈^[1].

Это единственный дистанционно-регулярный граф с массивом пересечений $\{7,4,1;1,2,7\}$ ; однако он не является дистанционно-транзитивным^[2].

Группой автоморфизмов 7-регулярного графа Клейна является та же самая группа порядка 336, что и для кубической карты Кляйна, действуя аналогично на полурёбра.

Характеристический многочлен — $(x-7)(x+1)^{7}(x^{2}-7)^{8}$ ^[3].

Примечания

↑ Schulte, Wills, 1985, с. 539–547.
↑ Brouwer, Cohen, Neumaier, 1989, с. 386.
↑ van Dam, Haemers, Koolen, Spence, 2006, с. 1805–1820.

Литература

Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).
Conder M., Dobcsányi P. Trivalent symmetric graphs up to 768 vertices // J. Combin. Math. Combin. Comput.. — 2002. — Т. 40. — С. 41–63.
Italo Dejter. From the Coxeter graph to the Klein graph // CiteSeer. — 2010. — arXiv:1002.1960.
Egon Schulte, Wills J. M. A Polyhedral Realization of Felix Klein's Map {3, 7}₈ on a Riemann Surface of Genus 3 // J. London Math. Soc.. — 1985. — Т. s2-32, вып. 3. — С. 539–547. — doi:10.1112/jlms/s2-32.3.539.
Andries Brouwer, Arjeh Cohen, Arnold Neumaier. Distance-Regular Graphs. — Springer-Verlag, 1989. — С. 398. — ISBN 978-0-387-50619-7.
van Dam E. R., Haemers W. H., Koolen J. H., Spence E. Characterizing distance-regularity of graphs by the spectrum // J. Combin. Theory Ser. A. — 2006. — Т. 113, вып. 8. — С. 1805–1820. — doi:10.1016/j.jcta.2006.03.008.

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

Обхват графа — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов, его обхват по определению равен бесконечности. Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников.

В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами.

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

<span class="mw-page-title-main">Дистанционно-транзитивный граф</span> такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, су

Дистанционно-транзитивный граф — граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.

Дистанционно-регулярный граф — такой регулярный граф, у которого для двух любых вершин $\text{[math]}$ и $\text{[math]}$ , расположенных на одинаковом расстоянии $\text{[math]}$ друг от друга, справедливо, что количество вершин, инцидентных к $\text{[math]}$ и при этом находящихся на расстоянии $\text{[math]}$ от вершины $\text{[math]}$ , зависит только от расстояния $\text{[math]}$ между вершинами $\text{[math]}$ и $\text{[math]}$ ; более того, количество вершин, инцидентных к $\text{[math]}$ и находящихся на расстоянии $\text{[math]}$ от вершины $\text{[math]}$ , также зависит только от расстояния $\text{[math]}$ .

<span class="mw-page-title-main">Граф Дезарга</span> дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами

Граф Дезарга — дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами. Назван в честь Жерара Дезарга. Возникает в некоторых комбинаторных построениях, имеет высокую степень симметрии, это единственный известный непланарный кубический частичный куб и применяется в химических базах данных.

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

Граф Татта — Коксетера — 3-регулярный граф с 30 вершинами и 45 рёбрами. Единственный наименьший кубический граф с обхватом 8, является клеткой и графом Мура. Двудольный и может быть построен как граф Леви обобщённого четырёхугольника W₂. Назван в честь Уильяма Томаса Татта и Гарольда Коксетера. Найден Уильямом Таттом, но его связь с геометрической комбинацией исследована обоими авторами в паре совместных статей.

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

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

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

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

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

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

<span class="mw-page-title-main">Граф Хэмминга</span> класс графов, названных именем Ричарда Хэмминга

Графы Хэмминга — специальный класс графов, названных именем Ричарда Хэмминга и используемых в некоторых областях математики и информатики.

Граф Шрикханде — граф, найденный С. С. Шрикханде в 1959 году. Граф сильно регулярен, имеет 16 вершин и 48 рёбер и каждая вершина имеет степень 6. Каждая пара узлов имеет ровно два общих соседа, независимо от того, связана эта пара ребром или нет.

Граф Госсета, названный именем Торолда Госсета, является 1-остовом 7-мерного многогранника 3₂₁. Это регулярный граф с 56 вершинами и валентностью 27.

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

Граф Уэлса — единственный дистанционно-регулярный граф с массивом пересечений $\text{[math]}$ .

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

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