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

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

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

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

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