Граф Фрухта — определённый планарный минимальный кубический граф, не имеющий нетривиальных автоморфизмов. Описан Робертом Фрухтом в 1939 году.
Свойства Граф Фрухта:
Не имеет нетривиальных симметрий; Имеет 12 вершин и 18 рёбер; Является кубическим графом; Является рёберно k-связным графом; Имеет радиус 3, диаметр 4, обхват 3, хроматическое число 3, хроматический индекс 3, число независимости равно 5; Граф Фрухта является гамильтоновым и задаётся LCF-кодом
Граф Фрухта — является также графом Халина.
Как и все графы Халина, граф Фрухта является планарным, 3-вершинно-связным и графом многогранника.
Граф Фрухта — один из минимальных кубических графов, имеющих единственный автоморфизм — тождественностьSkiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990 (таким образом, любая вершина может быть топологически отличима от остальных). Такие графы называются асимметричными графами. Теорема Фрухта утверждает, что любую группу можно представить как группу симметрий графа,. а усиление этой теоремы утверждает, что любая группа может быть представлена как группа симметрий 3-регулярного графа. Граф Фрухта даёт пример такой реализации для тривиальной группы.
Характеристический многочлен графа Фрухта равен .
Ссылки
Категория:Регулярные графы Категория:Графы, имеющие собственные названия Категория:Планарные графы