граф Фолкмана
В математической области теории графов граф Фолкмана , названный в честь Джона Фолкмана , представляет собой двудольный 4 - регулярный граф с 20 вершинами и 40 ребрами. [1]
Граф Фолкмана является гамильтоновым и имеет хроматическое число 2, хроматический индекс 4, радиус 3, диаметр 4 и обхват 4. Это также 4 -вершинно-связный и 4 -реберно-связный совершенный граф . Он имеет толщину книги 3 и номер очереди 2. [2]
Группа автоморфизмов графа Фолкмана действует транзитивно на его ребрах, но не на его вершинах. Это наименьший неориентированный граф, реберно-транзитивный и регулярный, но не вершинно-транзитивный . [3] Такие графы называются полусимметричными графами и были впервые изучены Фолкманом в 1967 году, который открыл граф на 20 вершинах, который теперь назван в его честь. [4]
Как полусимметричный граф, граф Фолкмана является двудольным , и его группа автоморфизмов действует транзитивно на каждом из двух наборов вершин двудольного разбиения. На приведенной ниже диаграмме с указанием хроматического числа графа зеленые вершины не могут быть отображены в красные никаким автоморфизмом, но любая красная вершина может быть отображена в любую другую красную вершину, а любая зеленая вершина может быть отображена в любую другую зеленую вершину. .
Характеристический полином графа Фолкмана равен .
