Граф Фрухта

Шаблон:Граф В теорії графів Графом Фрухта називається 3-регулярний граф з 12 вершинами і 18 ребрами без нетривіальних симетрій. Граф вперше був описаний Шаблон:Не перекладено в 1939 році.

Граф Фрухта — це граф Халіна з хроматичним числом 3, хроматичним індексом 3, радіусом 3, діаметром 4 і обхватом 3. Як і всі графи Халіна, граф Фрухта є планарним, 3-вершинно-зв'язним і багатогранним графом. Він також є k-реберно-зв'язним графом. Його число незалежності дорівнює 5.

Граф Фрухта є гамільтоновим і може бути побудований за LCF-записом [-5,-2,-4,2,5,-2,2,5,-2,-5,4,2].

Алгебраїчні властивості

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

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

Галерея

• 
  Хроматичне число графу Фрухта дорівнює 3.
• 
  Граф Фрухта є гамільтоновим.