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

Граф Фолкмана — это двудольный 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.
• Гамильтонов цикл в графе Фолкмана.