Граф Фолкмана (Ijgs Skltbgug)

Перейти к навигации Перейти к поиску
Граф Фолкмана
Граф Фолкмана
Граф Фолкмана
Назван в честь Дж. Фолкмана
Вершин 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].

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

Характеристический многочлен графа Фолкмана равен .

Примечания

[править | править код]
  1. Weisstein, Eric W. Folkman graph (англ.) на сайте Wolfram MathWorld.
  2. Wolz, 2018.
  3. Skiena, 1990, с. 186-187.
  4. Folkman, 1967, с. 215–232.

Литература

[править | править код]
  • Skiena S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading. — MA: Addison-Wesley, 1990.
  • Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).
  • Folkman J. Regular line-symmetric graphs // Journal of Combinatorial Theory. — 1967. — Т. 3, вып. 3. — doi:10.1016/S0021-9800(67)80069-3.