Русская Википедия:Граф Хоффмана
Граф Хоффмана является 4-регулярным графом с 16 вершинами и 32 рёбрами, который открыл Алан Хоффман[1] и опубликовал в 1963. Граф коспектрален графу гиперкуба Q4Шаблон:RШаблон:R.
Граф Хоффмана имеет много общих свойств с гиперкубом Q4 — оба гамильтоновы и имеют хроматическое число 2, хроматический индекс 4, обхват 4 и диаметр 4. Граф также вершинно 4-связен и рёберно 4-связен. Однако радиус графа Хоффмана равен 3 в отличие от гиперкуба Q4 (радиус которого равен 4)[1]. Граф Хоффмана не дистанционно-регулярен. Граф имеет книжную толщину 3 и число очередей 2Шаблон:R.
Алгебраические свойства
Граф Хоффмана не вершинно-транзитивен и его полная группа автоморфизмов является группой порядка 48, изоморфной прямому произведению симметрической группы S4 и циклической группы Z/2Z.
Характеристический многочлен графа Хоффмана равен
- <math>(x-4) (x-2)^4 x^6 (x+2)^4 (x+4)</math>,
что делает его целым графом — графом, спектр которого полностью состоит из целых чисел. Это тот же спектр, что и у гиперкуба Q4.
Галерея
-
Граф Хоффмана гамильтонов.
-
Хроматическое число графа Хоффмана равно 2.
-
Хроматический индекс графа Хоффмана равен 4.
Примечания
