Граф Грея

21.10.2021

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

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

Построение

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

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

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

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

[ − 25 , 7 , − 7 , 13 , − 13 , 25 ] 9 {displaystyle [-25,7,-7,13,-13,25]^{9}} .

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

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

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

( x − 3 ) x 16 ( x + 3 ) ( x 2 − 6 ) 6 ( x 2 − 3 ) 12 .   {displaystyle (x-3)x^{16}(x+3)(x^{2}-6)^{6}(x^{2}-3)^{12}. }

Галерея

  • Граф Грея

  • Хроматическое число графа Грея равно 2.

  • хроматический индекс графа Грея равен 3.

  • Конфигурация, лежащая в основе графа Грея.