Граф Грея

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

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

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

Построение

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

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

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

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

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

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

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

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

$(x-3)x^{16}(x+3)(x^{2}-6)^{6}(x^{2}-3)^{12}.\$

Галерея

• 
  Граф Грея
• 
  Хроматическое число графа Грея равно 2.
• 
  хроматический индекс графа Грея равен 3.
• 
  Конфигурация, лежащая в основе графа Грея.

Ссылки

• An edge but not vertex transitive cubic graph // Bulletin of the Canadian Mathematical Society. — 1968. — Т. 11. — С. 533–535. — doi:10.4153/CMB-1968-063-0..
• I. Z. Bouwer. On edge but not vertex transitive regular graphs // Journal of Combinatorial Theory, Series B. — 1972. — Т. 12. — С. 32–40. — doi:10.1016/0095-8956(72)90030-5..
• J. Folkman. Regular line-symmetric graphs // Journal of Combinatorial Theory. — 1967. — Т. 3, вып. 3. — С. 533–535. — doi:10.1016/S0021-9800(67)80069-3..
• Dragan Marušič, Tomaž Pisanski. The Gray graph revisited // Journal of Graph Theory. — 2000. — Т. 35. — С. 1–7. — doi:10.1002/1097-0118(200009)35:1<1::AID-JGT1>3.0.CO;2-7..
• Dragan Marušič, Tomaž Pisanski, Steve Wilson. The genus of the Gray graph is 7 // European Journal of Combinatorics. — 2005. — Т. 26, вып. 3–4. — С. 377–385. — doi:10.1016/j.ejc.2004.01.015..
• B. Monson, T. Pisanski, E. Schulte, A. Ivic-Weiss. Semisymmetric Graphs from Polytopes // Journal of Combinatorial Theory, Series A. — 2007. — Т. 114, вып. 3. — С. 421–435. — doi:10.1016/j.jcta.2006.06.007.
• Weisstein, Eric W. Gray Graph (англ.) на сайте Wolfram MathWorld.
• The Gray Graph Is the Smallest Graph of Its Kind Архивная копия от 22 февраля 2014 на Wayback Machine, from MathWorld.