Граф Коксетера — 3-регулярний граф з 28 вершинами і 42 ребрах. Усі кубічні дистанційно-регулярні графи відомі , граф Коксетера — один з 13-ти таких графів.
Властивості Хроматичне число графа 3, хроматичний індекс дорівнює 3, радіус дорівнює 4, діаметр — 4 обхват — 7. Граф є також вершинно 3-зв'язним і реберно 3-зв'язним.
Граф Коксетера є гіпогамільтоновим графом — сам по собі він не містить гамільтонових циклів, але видалення будь-якої вершини робить його гамільтоновим. Число прямолінійних схрещень графа Коксетера дорівнює 11 і це мінімальний відомий кубічний граф з таким числом схрещень, хоча графи з 26 вершинами і числом схрещень 11 існувати можуть.
Граф Коксетера можна побудувати з меншого дистанційно-регулярного графа Хівуда шляхом створення вершини для кожного 6-циклу в графі Хивуда і ребра для кожної незв'язної пари 6-циклів..
Граф Коксетера також можна отримати з графа Гофмана — Синглтона. Візьмемо будь яку вершину v графа Гофмана — Синглтона. Існує незалежна множина розміру 15, яка містить v. Видалимо 6 сусідів v і цю незалежну множину, включаючи v залишимо.
Алгебраїчні властивості Група автоморфізмів графа Коксетера — це група порядку 336Royle, G. F028A data. Вона діє транзитивно на вершини і ребра графа, тому граф Коксетера є симетричним. Граф має автоморфизми, які переводять будь-яку вершину в будь-яку іншу і будь-яке ребро будь-яке інше ребро. У «списку Фостера» граф Коксетера, зазначений як F28A, є єдиним кубічним симетричним графом з 28 вершинамиM. Conder, P. Dobcsányi, «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002..
Граф Коксетера однозначно визначається за його спектром, тобто множиною власних значень матриці суміжності графаE. R. van Dam and W. H. Haemers, Spectral Characterizations of Some Distance-Regular Graphs. J. Алгебраїчна Combin. 15, pages 189—202, 2003.
Як скінченно зв'язний вершинно-транзитивний граф, що не містить гамільтонових циклів, граф Коксетера є контрприкладом варіанту гіпотези Ловаса, але канонічна формулювання гіпотези вимагає наявності гамільтонового циклу.
Відомо лише п'ять вершинно-транзитивних графів без гамільтонових циклів — повний граф «K»2, граф Петерсена, граф Коксетера і два графи, отримані з графів Петерсена і Коксетера шляхом заміни кожної вершини трикутникомRoyle, G. «Cubic Symmetric Graphs (Foster The Census).» .
Характеристичний поліном графа Коксетера дорівнює . Граф є єдиним графом з таким поліномом, що і дозволяє однозначно визначити граф Коксетера за його спектром.
Галерея
Примітки