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

Свойства

Граф Фрухта:

• Не имеет нетривиальных симметрий ;

• Имеет 12 вершин и 18 рёбер;

• Является кубическим графом ;

• Является рёберно k-связным графом ;

• Имеет радиус 3, диаметр 4, обхват 3, хроматическое число 3, хроматический индекс 3, число независимости равно 5;

• Граф Фрухта является гамильтоновым и задётся LCF-кодом

  ${\displaystyle [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2].}$

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

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

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

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

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

Ссылки