26-фуллереновый граф

26-фуллерен
Граф 26-фуллерена с выделенными шестиугольниками
Вершины	26
Края	39
Радиус	5
Диаметр	6
Обхват	5
Хроматическое число	3
Хроматический индекс	3
Характеристики	грани = 3 шестиугольника, 12 пятиугольников
Таблица графиков и параметров

В математической области теории графов граф 26-фуллеренов — это многогранный граф с V  = 26 вершинами и E  = 39 ребрами. Его планарное вложение имеет три шестиугольные грани (включая ту, которая показана как внешняя грань на рисунке) и двенадцать пятиугольных граней. Как планарный граф только с пятиугольными и шестиугольными гранями, встречающимися в трех гранях на вершину, этот граф является фуллереном . Существование этого фуллерена известно по крайней мере с 1968 года. ^[1]

Граф 26-фуллеренов имеет призматическую симметрию , ту же группу симметрий, что и треугольная призма . Эта группа симметрии имеет 12 элементов; она имеет шесть симметрий, которые произвольно переставляют три шестиугольные грани графа и сохраняют ориентацию его плоского вложения, и еще шесть симметрий, меняющих ориентацию. ^[2]${\displaystyle D_{3h}}$

Число фуллеренов с заданным четным числом вершин быстро растет с числом вершин; 26 — наибольшее число вершин, для которого структура фуллерена уникальна. Единственными двумя меньшими фуллеренами являются граф правильного додекаэдра (фуллерен с 20 вершинами) и граф усеченного гексагонального трапецоэдра (фуллерен с 24 вершинами), ^[3] , которые являются двумя типами ячеек в структуре Уэйра–Фелана .

Граф 26-фуллеренов имеет много идеальных паросочетаний . Нужно удалить по крайней мере пять ребер из графа, чтобы получить подграф, который имеет ровно одно идеальное паросочетание. Это уникальное свойство этого графа среди фуллеренов в том смысле, что для любого другого числа вершин фуллерена существует по крайней мере один фуллерен, из которого можно удалить четыре ребра, чтобы получить подграф с уникальным идеальным паросочетанием. ^[4]

Вершины графа 26-фуллеренов можно пометить последовательностями из 12 бит таким образом, что расстояние в графе будет равно половине расстояния Хэмминга между этими битвекторами . Это также можно интерпретировать как изометрическое вложение графа в 12-мерную геометрию такси . Граф 26-фуллеренов является одним из пяти фуллеренов с таким вложением. ^[2]

В 2009 году газета The New York Times опубликовала головоломку с гамильтоновыми путями в этом графе, используя соответствие между его 26 вершинами и 26 буквами английского алфавита. ^{[5] [6]}