Граф Фолкмана

Граф Фолкмана
Граф Фолкмана
Назван в честь	Дж. Фолкмана
Вершин	20
Рёбер	40
Радиус	3
Диаметр	4
Обхват	4
Автоморфизмы	3840
Хроматическое число	2
Хроматический индекс	4
Свойства	Двудольный Гамильтонов Полусимметричный Регулярный Эйлеров Совершенный
Медиафайлы на Викискладе

Граф Фолкмана (названный именем Джона Фолкмана) — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами^[1].

Граф Фолкмана является гамильтоновым и имеет хроматическое число 2, хроматический индекс 4, радиус 3, диаметр 4 и обхват 4. Он также является вершинно 4-связным, рёберно 4-связным и совершенным. Граф имеет книжное вложение 3 и число очередей 2^[2].

Алгебраические свойства

Группа автоморфизмов графа Фолкмана действует транзитивно на его рёбра, но не на его вершины. Это наименьший неориентированный граф, который является рёберно-транзитивным и регулярным, но не вершинно транзитивным^[3]. Такие графы называются полусимметричными, их первым изучал Фолкман в 1967 и обнаружил граф с 20 вершинами, который был позже назван его именем^[4].

Как полусимметричный граф, граф Фолкмана является двудольным и его группа автоморфизмов действует транзитивно на каждую долю вершин двудольного графа. На диаграмме ниже, показывающей хроматическое число графа, зелёные вершины не могут быть отражены в красные каким-либо автоморфизмом, но любая красная вершина может быть отражена в любую другую красную вершину, а любая зелёная — в любую другую зелёную вершину.

Характеристический многочлен графа Фолкмана равен ${\displaystyle (x-4)x^{10}(x+4)(x^{2}-6)^{4}}$.

Галерея

• 
  Хроматический индекс графа Фолкмана равен 4.
• 
  Хроматическое число графа Фолкмана равно 2.
• 
  Граф Фолкмана является гамильтоновым.

Примечания

Литература

Эта страница в последний раз была отредактирована 15 апреля 2019 в 17:52.