WikiSort.ru - Не сортированное

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

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

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

Галерея

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.