Граф Фолкмана

14-05-2021, 13:40

Граф Фолкмана (названный именем Джона Фолкмана) — это двудольный 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.

  • Граф Фолкмана является гамильтоновым.


  • Ядро (теория графов)
  • Лестница Мёбиуса
  • Граф Холта
  • Граф Дюрера
  • Граф Леви

  •  

    • Яндекс.Метрика
    • Индекс цитирования