| Граф Хоффмана | |
|---|---|
 | |
| Назван в честь | Алана Хоффмана |
| Вершин | 16 |
| Рёбер | 32 |
| Радиус | 3 |
| Диаметр | 4 |
| Обхват | 4 |
| Хроматическое число | 2 |
| Хроматический индекс | 4 |
| Свойства |
Гамильтонов Двудольный Совершенный Эйлеров |
| Книжная толщина | 3 |
| Число очередей | 2 |
 Медиафайлы на Викискладе | |
Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман[1] и опубликовал в 1963. Граф коспектрален графу гиперкуба Q4[2][3].
Граф Хоффмана имеет много общих свойств с гиперкубом Q4 — оба гамильтоновы и имеют хроматическое число 2, хроматический индекс 4, обхват 4 и диаметр 4. Граф также вершинно 4-связен и рёберно 4-связен. Однако радиус графа Хоффмана равен 3 в отличие от гиперкуба Q4 (радиус которого равен 4)[1]. Граф Хоффмана не дистанционно-регулярен. Граф имеет книжную толщину 3 и число очередей 2[4].
Алгебраические свойства
Граф Хоффмана не вершинно-транзитивен и его полная группа автоморфизмов является группой порядка 48, изоморфной прямому произведению симметрической группы S4 и циклической группы Z/2Z.
Характеристический многочлен графа Хоффмана равен
- ,
что делает его целым графом — графом, спектр которого полностью состоит из целых чисел. Это тот же спектр, что и у гиперкуба Q4.
Галерея
-
Граф Хоффмана гамильтонов. -
Хроматическое число графа Хоффмана равно 2. -
Хроматический индекс графа Хоффмана равен 4.
Примечания
- ↑ 1 2 Weisstein, Eric W. Hoffman graph (англ.) на сайте Wolfram MathWorld.
- ↑ Hoffman A. J. On the Polynomial of a Graph // Amer. Math. Monthly. — 1963. — Т. 70. — С. 30-36.
- ↑ van Dam E. R., Haemers W. H. Spectral Characterizations of Some Distance-Regular Graphs // J. Algebraic Combin.. — 2003. — Т. 15. — С. 189-202.
- ↑ Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).
Эта страница в последний раз была отредактирована 23 января 2022 в 20:32.
Обычно почти сразу, изредка в течении часа.