Граф Фрухта

Граф Фрухта:

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

• Имеет 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] (таким образом, любая вершина может быть топологически отличима от остальных). Такие графы называются асимметричными графами.
  • Теорема Фрухта утверждает, что любую группу можно представить как группу симметрий графа,^[1] а усиление этой теоремы, тоже Фрухта, утверждает, что любая группа может быть представлена как группа симметрий 3-регулярного графа^[4] Граф Фрухта даёт пример такой реализации для тривиальной группы.

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