Граф Грея

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

Граф Грея
Назван в честь Марион Камерон Грей
Вершин 54
Рёбер 81
Радиус 6
Диаметр 6
Обхват 8
Автоморфизмы 1296
Хроматическое число 2
Хроматический индекс 3
Свойства

полусимметричный
кубический


гамильтонов

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

Построение

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

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

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

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

.

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

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

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

Галерея

Примечания

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.