Граф Госсета

Перейти к навигацииПерейти к поиску
Граф Госсе
Граф Госсета (321) (Имеется 3 кольца по 18 вершин и две вершины в центре рисунка совпадают в этой проекции. Рёбра также совпадают.)
Граф Госсета (321)
(Имеется 3 кольца по 18 вершин и две вершины в центре рисунка совпадают в этой проекции. Рёбра также совпадают.)
Назван в честь Торолда Госсета
Вершин 56
Рёбер 756
СвойстваДистанционно-регулярный
Целый граф
Вершинно-транзитивный

Граф Госсета, названный именем Торолда Госсета, является 1-остовом[англ.] 7-мерного многогранника 321[англ.]. Это регулярный граф с 56 вершинами и валентностью 27[1].

Построение

Граф Госсета можно построить явно следующим образом. 56 вершин — это вектора в R8, полученные перестановкой координат вектора (28 вершин) и противоположные им вектора (ещё 28 вершин). Два таких вектора соединены ребром, если их скалярное произведение равно 8.

Альтернативное построение основывается на полном графе K8 с 8 вершинами. Вершины графа Госсета можно отождествить с двумя копиями рёбер графа K8. Две вершины графа Госсета тогда из одной копии соединены ребром, если они соответствуют несмежным рёбрам графа K8. Две вершины, полученные из разных копий связаны ребром, если они соответствуют рёбрам, имеющим одну общую вершину[2].

Свойства

В векторном представлении графа Госсета две вершины находятся на расстоянии два, когда их скалярное произведение равно -8 и на расстоянии три, если их скалярное произведение равно -24 (что возможно, только когда вектора симметричны относительно начала координат). В представлении на основе рёбер графа K8 две вершины графа Госсета находятся на расстоянии три тогда и только тогда, когда они соответствуют двум копиям одного и того же ребра графа K8. Граф Госсета является дистанционно-регулярным с диаметром три[3].

Порождённый подграф соседей любой вершины в графе Госсета изоморфен графу Шлефли[3].

Группа автоморфизмов графа Госсета изоморфен группе Коксетера E7[англ.], а потому имеет порядок 2903040. Многогранника Госсета 321 является полуправильным многогранником. Поэтому автоморфизм группы графа Госсета E7 действует транзитивно на его вершины, что делает его вершинно-транзитивным.

Характеристический многочлен графа Госсета равен[4].

Таким образом, этот граф является целым графом.

Литература

  1. ↑ В. П. Гришухин. Многогранники Делоне и Вороного корневой решетки и двойственной решетки  // Труды МИАН (Сборник статей. К 120-летию со дня рождения члена-корреспондента АН СССР Бориса Николаевича Делоне). — М.: МАИК «Наука/Интерпериодика», 2011. — Т. 275. — С. 68–86. — doi:10.1134/S0081543811080049..
  2. ↑ Willem H. Haemers. Distance-regularity and the spectrum of graphs // Linear Algebra and its Applications. — 1996. — Т. 236. — С. 265–278. — doi:10.1016/0024-3795(94)00166-9..
  3. ↑ 1 2 Kabanov V. V., Makhnev A. A., Paduchikh D. V. Characterization of some distance-regular graphs by forbidden subgraphs // Doklady Akademii Nauk. — 2007. — Т. 414, вып. 5. — С. 583–586. — doi:10.1134/S1064562407030234..
  4. ↑ Brouwer A. E., Riebeek R. J. The spectra of Coxeter graphs // Journal of Algebraic Combinatorics. — 1998. — Т. 8, вып. 1. — С. 15–28. — doi:10.1023/A:1008670825910..

Ссылки