Перегляд вихідного коду сторінки Граф Коксетера

{{Граф
 | name     = 
 | image    = [[файл:Coxeter_graph.svg|250пкс]]
 | image_caption = Граф Коксетера
 | namesake = 
 | vertices = 28
 | edges    = 42
 | radius   = 4
 | diameter = 4
 | girth    = 7
 | automorphisms = 336 ([[Проективна група|ПЛГ]]<sub>2</sub>(7))
 | chromatic_number = 3
 | chromatic_index  = 3
 | fractional_chromatic_number = 
 | fractional_chromatic_index  = 
 | genus = 
 | spectral_gap =
 | queue_number = 2
 | properties = [[Симетричний граф|симетричний]]<br/>[[Кубічний граф|кубічний]]<br/>[[Дистанційно-регулярний граф|дистанційно-регулярний]]<br/>[[Дистанційно-транзитивний граф|дистанційно-транзитивний]]<br/>{{Нп|Гіпогамільтонів граф|гіпогамільтонів||Hypohamiltonian graph}}
}}
{{Також|Коксетер}}
'''Граф Коксетера'''&nbsp;— 3-[[регулярний граф]] з 28 вершинами і 42 ребрах<ref>{{MathWorld|urlname = CoxeterGraph|title = Coxeter Graph}}</ref>. Усі [[Кубічний граф|кубічні]] [[Дистанційно-регулярний граф|дистанційно-регулярні]] графи відомі<ref>{{книга|автор = A. E. Брауер, A. M. Cohen, A. Neumaier|заголовок = Distance-Regular Graphs.|місце = New York|видавництво = Springer-Verlag|рік = 1989}} {{ref-en}}</ref>, граф Коксетера&nbsp;— один з 13-ти таких графів.

== Властивості ==
[[Хроматичне число]] графа 3, [[хроматичний індекс]] дорівнює 3, [[Словник термінів теорії графів#Р|радіус]] дорівнює 4, [[Словник термінів теорії графів#Д|діаметр]]&nbsp;— 4 [[Обхват (теорія графів)|обхват]]&nbsp;— 7. Граф є також [[k-вершинно-зв'язний граф|вершинно 3-зв'язним]] і [[k-реберно-зв'язний граф|реберно 3-зв'язним]].

Граф Коксетера є гіпогамільтонівським графом&nbsp;— сам по собі він не містить гамільтонових циклів, але видалення будь-якої вершини робить його [[Гамільтонів граф|гамільтоновим]].
[[Число схрещень|Число прямолінійних схрещень]] графа Коксетера дорівнює 11 і це мінімальний відомий кубічний граф з таким числом схрещень, хоча графи з 26 вершинами і числом схрещень 11 існувати можуть<ref>{{OEIS|id = A110507}}</ref>.

Граф Коксетера можна побудувати з меншого дистанційно-регулярного [[Граф Хівуда|графа Хівуда]] шляхом створення вершини для кожного 6-циклу в графі Хивуда і ребра для кожної незв'язної пари 6-циклів.<ref>{{стаття
|автор = Italo J. Dejter|заголовок = From the Coxeter graph to the graph Klein|видання = Journal of теорія Графів|рік = 2011|doi = 10.1002/jgt.20597|arxiv = 1002.1960}}.</ref>

Граф Коксетера також можна отримати з [[Граф Гофмана — Синглтона|графа Гофмана&nbsp;— Синглтона]]. Візьмемо будь яку вершину ''v'' графа Гофмана&nbsp;— Синглтона. Існує [[Задача про незалежну множину|незалежна множина]] розміру 15, яка містить ''v''. Видалимо 6 сусідів ''v'' і цю незалежну множину, включаючи ''v'' залишимо.


== Алгебраїчні властивості ==
Група автоморфізмів графа Коксетера&nbsp;— це група порядку 336<ref>Royle, G. [http://www.csse.uwa.edu.au/~gordon/foster/F028A.html F028A data]{{Недоступне посилання|date=квітень 2019 |bot=InternetArchiveBot }}</ref>. Вона [[Дія групи|діє]] транзитивно на вершини і ребра графа, тому граф Коксетера є [[Симетричний граф|симетричним]]. Граф має автоморфизми, які переводять будь-яку вершину в будь-яку іншу і будь-яке ребро будь-яке інше ребро. У «списку Фостера» граф Коксетера, зазначений як F28A, є єдиним кубічним симетричним графом з 28 вершинами<ref>M. Conder, P. Dobcsányi, «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002.</ref>.

Граф Коксетера однозначно визначається за його [[Спектральна теорія графів|спектром]], тобто множиною власних значень [[Матриця суміжності|матриці суміжності]] графа<ref>E. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Алгебраїчна Combin. 15, pages 189—202, 2003</ref>.

Як скінченно зв'язний вершинно-транзитивний граф, що не містить [[Гамільтонів граф|гамільтонових циклів]], граф Коксетера є контрприкладом варіанту [[Гіпотеза Ловаса про гамільтонів цикл|гіпотези Ловаса]], але канонічна формулювання гіпотези вимагає наявності гамільтонового циклу.

Відомо лише п'ять вершинно-транзитивних графів без гамільтонових циклів&nbsp;— [[повний граф]] «K»<sub>2</sub>, [[граф Петерсена]], граф Коксетера і два графи, отримані з графів Петерсена і Коксетера шляхом заміни кожної вершини трикутником<ref>Royle, G. [http://www.cs.uwa.edu.au/~gordon/remote/foster/#census «Cubic Symmetric Graphs (Foster The Census).»] {{Webarchive|url=https://web.archive.org/web/20080720005020/http://www.cs.uwa.edu.au/~gordon/remote/foster/#census |date=20 липня 2008 }}</ref>.

[[Характеристичний поліном]] графа Коксетера дорівнює <math>(x-3) (x-2)^8 (x+1)^7 (x^2+2 x-1)^6</math>. Граф є єдиним графом з таким поліномом, що і дозволяє однозначно визначити граф Коксетера за його спектром.

== Галерея ==
<gallery>
Файл:Edge excised Coxeter graph.svg|Граф, отриманий видаленням будь-якого ребра з графа Коксетера є  [[Гамільтонів шлях|гамільтоново-зв'язним]].
Файл:coxeter_graph_3COL.svg|[[Розфарбовування графів|Хроматичне число]] графа Коксетера дорівнює 3.
Файл:Coxeter graph 11C.svg|[[Число схрещень|Число прямолінійних схрещень]] графа Коксетера дорівнює 11.
</gallery>

== Примітки ==
{{примітки}}

[[Категорія:Регулярні графи]]
[[Категорія:Графи, що мають власну назву]]