Граф Фрухта

Граф Фрухта — определённый планарный минимальный кубический граф, не имеющий нетривиальных автоморфизмов. Описан Робертом Фрухтом в 1939 году.

Свойства

Граф Фрухта:

• Не имеет нетривиальных симметрий;
• Имеет 12 вершин и 18 рёбер;
• Является кубическим графом;
• Является рёберно k-связным графом;
• Имеет радиус 3, диаметр 4, обхват 3, хроматическое число 3, хроматический индекс 3, число независимости равно 5;
• Граф Фрухта является гамильтоновым и задаётся LCF-кодом

  $[-5,-2,2,3,-2,4,-3,5,2,-4,-2,2].$

• 
  Раскраска в три цвета.
• 
  Гамильтонов цикл.

• Граф Фрухта — это граф Халина.

• Как и все графы Халина, граф Фрухта является планарным, 3-вершинно-связным и графом многогранника.

• Граф Фрухта — один из минимальных кубических графов, имеющих единственный автоморфизм — тождественность (таким образом, любая вершина может быть топологически отличима от остальных). Такие графы называются асимметричными графами.
  • Теорема Фрухта утверждает, что любую группу можно представить как группу симметрий графа, а усиление этой теоремы, тоже Фрухта, утверждает, что любая группа может быть представлена как группа симметрий 3-регулярного графа Граф Фрухта даёт пример такой реализации для тривиальной группы.

• Характеристический многочлен графа Фрухта равен $(x-3)(x-2)x(x+1)(x+2)(x^3+x^2-2x-1)(x^4+x^3-6x^2-5x+4)$.