Граф Грея

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

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

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

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

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

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

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

${\displaystyle (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, from MathWorld.