Граф Хівуда

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

Граф Хівуда
Названий на честь Персі Джон Хівуд
Вершин 14
Ребер 21
Радіус 3
Діаметр 3
Обхват 6
Автоморфізм 336 (PGL2(7))
Хроматичне число 2
Хроматичний індекс 3
Властивості Двочастковий
Кубічний
дистанційно-транзитивний
дистанційно-регулярний
тороїдальний
гамільтонів
Симетричний

Комбінаторні властивості

Граф є кубічним і всі цикли в графі містять шість і більше ребер. Менший кубічний граф містить менші цикли, так що цей граф є (3,6) -кліткою, найменшим кубічним графом з обхватом 6. Він є також дистанційно-транзитивним (дивіться список Фостера), а тому дистанційно-регулярним[2].У графі Хівуда мається 24 паросполучення, і у всіх паросполучень ребра, що не входять у паросполучення, утворюють гамільтонів цикл. Наприклад, малюнок показує вершини графу, поміщені на окружність і що утворюють цикл, а діагоналі всередині кола утворюють паросполучення. Якщо розділити ребра циклу на два паросполучення, ми отримаємо три абсолютні паросполучення (тобто, 3-кольорову розмальовку ребер) вісьмома різними способами[2]. Зважаючи симетрії графу будь-які два досконалих парування і будь-які два гамільтонових цикли можна перетворити з одного в інше[3].

У графі Хівуда 28 циклів, що містять по шість вершин. Кожен такий цикл не пов'язаний в точності з трьома іншими 6-вершинними циклами. Серед цих трьох циклів кожен є симетричної різницею двох інших. Граф в якому кожна вершина відповідає циклу з 6 вершин графу Хівуда, а дуги відповідають незв'язним парам — це граф Коксетера.[4].

Геометричні та топологічні властивості

Граф Хівуда є тороїдальним графом, тобто його можна вкласти без перетинів в тор. Одне з вкладень такого типу розміщує вершини і ребра графу в тривимірному евклідовому просторі у вигляді безлічі вершин і ребер неопуклого багатогранника з топологією тора, багатогранника Сілаші. Граф названий на честь Персі Джона Хівуда, який довів у 1890 році, що для розмальовки будь-якого розбиття тора на багатокутники достатньо семи кольорів[5][6]. Граф Хівуда утворює розбиття тора на сім взаємно суміжних областей, що показує, що кордон точна. Граф Хівуда є також графом Леві поверхні Фано, тобто графом, що представляє инцидентность точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано,тобто графом, представленим iнцидентнiсть точок і прямих в цій геометрії. У цій інтерпретації цикли довжини 6 в графі Хівуда відповідають трикутникам поверхні Фано. Граф Хівуда має число схрещувань рівне 3 і є найменшим кубічним графом з таким числом схрещувань[7]. Разом з графом Хівуда існує 8 різних графів порядку 14 з числом схрещувань 3. Граф Хівуда є графом одиничних відстаней — його можна вкласти в площину так, що суміжні вершини опиняться в точності на відстані одиниця, при цьому ніякі дві вершини не потраплять на одне і те ж місце площині і ніяка крапка не виявиться всередині ребра. Однак у відомих вкладень цього типу відсутня симетрія, притаманна графу[8].

Алгебраїчні властивості

Група автоморфізмів графу Хівуда ізоморфна проективної лінійної групою PGL22(7), групі порядку 336[9].Він діє транзитивно на вершини, на ребра і на дуги графу, тому граф Хівуда є симетричним. Є автоморфізм, що переводять будь-яку вершину в будь-яку іншу вершину і будь ребро в будь-яке інше ребро. Згідно зі списком Фостера граф Хівуда, позначений як F014A, є єдиним кубічним графом з 14 вершинами[10][11]. Характеристичний многочлен матриці графу Хівуда . Спектр графу дорівнює .Це єдиний граф з таким многочленом, який визначається спектром.

Хроматичний многочлен графу дорівнює:

.

Галерея

Примітки

  1. Weisstein, Eric W. Heawood Graph(англ.) на сайті Wolfram MathWorld.
  2. . Brouwer, Andries E.. Heawood graph. Additions and Corrections to the book “Distance-Regular Graphs” (Brouwer, Cohen, Neumaier; Springer; 1989).
  3. M. Abreu, R. E. L. Aldred, M. Funk, Bill Jackson, D. Labbate, J. Sheehan. Graphs and digraphs with all 2-factors isomorphic // Journal of Combinatorial Theory. — 2004. — Т. 92, вип. 2. — С. 395—404. DOI:10.1016/j.jctb.2004.09.004..
  4. Italo J. Dejter. From the Coxeter graph to the Klein graph // Journal of Graph Theory. — 2011. arXiv:1002.1960. DOI:10.1002/jgt.20597..
  5. Ezra Brown. The many names of (7,3,1) // Mathematics Magazine. — 2002. — Т. 75, вип. 2. — С. 83—94. DOI:10.2307/3219140. JSTOR 3219140.
  6. P. J. Heawood. Map colouring theorems // Quarterly J. Math. Oxford Ser. — 1890. — Т. 24. — С. 322—339.
  7. послідовність A110507 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
  8. Eberhard H., A. Gerbracht. Eleven unit distance embeddings of the Heawood graph. — 2009. arXiv:0912.5395..
  9. J. A. Bondy, U. S. R. Murty. {{{Заголовок}}}. — ISBN 0-444-19451-7.
  10. Royle, G. «Кубические симметричные графы (список Фостера).» Архівовано 20 липня 2008 у Wayback Machine.
  11. Марстон Кондер и Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41—63, 2002.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.