Граф Фолкмана — это двудольный 4-регулярный граф с 20 вершинами и 40 рёбрами, названный в честь Джона Фолкмана.
Граф Фолкмана является гамильтоновым и имеет хроматическое число 2, хроматический индекс 4, радиус 3, диаметр 4 и обхват 4. Он также является вершинно 4-связным, рёберно 4-связным и совершенным. Граф имеет книжное вложение 3 и число очередей 2.
Алгебраические свойства Группа автоморфизмов графа Фолкмана действует транзитивно на его рёбра, но не на вершины. Это наименьший по числу вершин неориентированный граф, который является рёберно-транзитивным и регулярным, но не вершинно-транзитивным. Такие графы называются полусимметричными; их первым начал изучать Фолкман, который в 1967 году построил граф с 20 вершинами, позже названный его именем.
Как полусимметричный граф, граф Фолкмана является двудольным, и его группа автоморфизмов действует транзитивно на каждую из двух долей вершин. На диаграмме, показывающей раскраску графа (в разделе «Галерея»), зелёные вершины не могут быть отображены в красные каким-либо автоморфизмом, однако любая красная вершина может быть отображена в любую другую красную, а любая зелёная — в любую другую зелёную.
Характеристический многочлен графа Фолкмана равен .
Галерея
Примечания
Литература
Категория:Графы, имеющие собственные названия Категория:Регулярные графы