Граф Грея

Шаблон:Граф

Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами. Граф является кубическим — любая вершина принадлежит ровно трём рёбрам. Граф был открыт Шаблон:Не переведено 5 в 1932 году (без публикации), затем открыт независимо Баувером (Bouwer) в 1968 году в ответ на вопрос, поставленный Шаблон:Не переведено 5 в 1967 году. Граф Грея примечателен как исторически первый пример кубического графа, имеющего алгебраическое свойство рёберной, но не вершинной транзитивности.

Хроматическое число графа Грея равно 2, хроматический индекс — 3, радиус и диаметр равны 6. Он также является вершинно 3-связным и рёберно 3-связным непланарным графом.

Построение

Граф Грея можно построитьШаблон:Sfn из 27 точек решётки размером 3×3×3 и 27 прямых, параллельных осям и проходящих через эти точки. Этот набор точек и прямых образует проективную конфигурацию — через каждую точку проходят ровно три прямых и на каждой прямой лежат ровно три точки. Граф Грея является графом Леви этой конфигурации. Граф имеет вершину для каждой точки и для каждой прямой этой конфигурации и ребро для каждой пары точка-прямая, если точка лежит на прямой. Эта конструкция может быть обобщена (Баувер, 1972) на любую размерность $n ⩾ 3$ , давая $n$ -валентные графы Леви с алгебраическими свойствами, похожими на свойства графа Грея.

Также может быть построен как граф Леви для рёбер и треугольных граней некоторого локально тороидального абстрактного правильного 4-многогранникаШаблон:Sfn.

Марушич и ПисанскиШаблон:Sfn дали некоторые альтернативные методы построения графа Грея. Как и любой другой двудольный граф, граф Грея не содержит циклов нечётной длины, а также не содержит циклов с четырьмя или шестью вершинами, так что обхват графа Грея равен 8. Самая простая ориентированная поверхность, в которую граф Грея можно вложить, имеет род 7Шаблон:Sfn.

Граф Грея является гамильтоновым и может быть построен из LCF-нотации:

[- 25, 7, - 7, 13, - 13, 25]^{9}

.

Алгебраические свойства

Группа автоморфизмов графа Грея — это группа порядка 1296. Она действует транзитивно на рёбра графа, но не на его вершины — имеются автоморфизмы, переводящие любое ребро в любое другое ребро, но нет автоморфизмов, которые переводят любую вершину в любую другую. Вершины, соответствующие конфигурации, лежащей в основе графа, могут быть симметричны только вершинам, соответствующим точкам конфигурации, а вершины, соответствующие прямым, симметричны только вершинам, соответствующим прямым. Таким образом, граф Грея является Шаблон:Не переведено 5 и является наименьшим возможным кубическим полусимметричным графом.

Характеристический многочлен графа Грея равен: