Главная
Граф Фолкмана (названный именем Джона Фолкмана) — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами.
Граф Фолкмана является гамильтоновым и имеет хроматическое число 2, хроматический индекс 4, радиус 3, диаметр 4 и обхват 4. Он также является вершинно 4-связным, рёберно 4-связным и совершенным. Граф имеет книжное вложение 3 и число очередей 2.
Алгебраические свойства
Группа автоморфизмов графа Фолкмана действует транзитивно на его рёбра, но не на его вершины. Это наименьший неориентированный граф, который является рёберно-транзитивным и регулярным, но не вершинно транзитивным. Такие графы называются полусимметричными, их первым изучал Фолкман в 1967 и обнаружил граф с 20 вершинами, который был позже назван его именем.
Как полусимметричный граф, граф Фолкмана является двудольным и его группа автоморфизмов действует транзитивно на каждую долю вершин двудольного графа. На диаграмме ниже, показывающей хроматическое число графа, зелёные вершины не могут быть отражены в красные каким-либо автоморфизмом, но любая красная вершина может быть отражена в любую другую красную вершину, а любая зелёная — в любую другую зелёную вершину.
Характеристический многочлен графа Фолкмана равен ( x − 4 ) x 10 ( x + 4 ) ( x 2 − 6 ) 4 {displaystyle (x-4)x^{10}(x+4)(x^{2}-6)^{4}} .
Галерея
-
Хроматический индекс графа Фолкмана равен 4.
-
Хроматическое число графа Фолкмана равно 2.
-
Граф Фолкмана является гамильтоновым.