WikiSort.ru - Не сортированное

граф Шрикханде
Назван в честь	С. С. Шрикханде
Вершин	16
Рёбер	48
Радиус	2
Диаметр	2
Обхват	3
Автоморфизмы	192
Хроматическое число	4
Хроматический индекс	6
Свойства	Сильно регулярный Гамильтонов Симметричный Эйлеров Целый[en]
Книжная толщина	4
Число очередей	3

Граф Шрикханде — это граф, найденный С. С. Шрикханде в 1959 году^[1][2]. Граф сильно регулярен, имеет 16 вершин и 48 рёбер и каждая вершина имеет степень 6. Каждая пара узлов имеет ровно два общих соседа, независимо от того, связана эта пара или нет ребром.

Построение

Граф Шрикханде можно построить как граф Кэли, в котором множество вершин — это ${\displaystyle \mathbb {Z} _{4}\times \mathbb {Z} _{4}}$ , а две вершины связаны тогда и только тогда, когда разность находится в ${\displaystyle \{\pm (1,0),\pm (0,1),\pm (1,1)\}}$ .

Свойства

В графе Шрикханде любые две вершины I и J имеют двух различных общих соседей (исключая сами вершины I и J), что выполняется вне зависимости от того, смежны ли I и J, или нет. Другими совами, граф сильно регулярен и его параметрами являются: {16,6,2,2}, то есть, ${\displaystyle \lambda =\mu =2}$ . Из этого равенства следует, что граф ассоциирован с симмтреичными сбалансированными неполными блок-схемами (англ. Balanced Incomplete Block Designs, BIBD). Граф Шрикханде разделяет эти параметры с точно одним другим графом, 4×4 ладейным графом, то есть рёберным графом L(K_4,4) полного двудольного графа K_4,4. Последний граф является единственным рёберным графом L(K_{n, n}), для которого параметры сильной регулярности не определяют этот граф единственным образом, и граф делит их с другим графом, а именно, графом Шрикханде (который не является ладейным графом)^[2][3].

Граф Шрикханде локально шестиуголен. То есть, соседи каждой вершины образуют цикл из шести вершин. Как и любой локально цикличный граф, граф Шрикханде является 1-мерным остовом^[en] триангуляции Уитни некоторой поверхности. В случае графа Шрикханде эта поверхность является тором, в котором каждая вершина окружена шестью треугольниками^[4] Таким образом, граф Шрикханде — это тороидальный граф. Вложение образует регулярное отображение в тор с 32 треугольными гранями. Остов дуального графа этого отображения (как вложенного в тор) — граф Дика, кубический симметричный граф.

Граф Шрикханде не является дистанционно-транзитивным. Это самый маленький дистанционно-регулярный граф, не являющийся дистанционно-транзитивным^[5].

Группа автоморфизмов графа Шрикханде имеет порядок 192. Она действует транзитивно нf вершины, на рёбра и дуги графа. Поэтому граф Шрикханде является симметричным графом.

Характеристический многочлен графа Шрикханде равен ${\displaystyle (x-6)(x-2)^{6}(x+2)^{9}}$ . Таким образом, граф Шрикханде является целым графом^[en] — его спектр состоит всецело из целых чисел.

Граф имеет книжную толщину 4 и число очередей 3^[6].

Галерея

• 
  Граф Шрикханде является тороидальным.
• 
  Хроматическое число графа Шрикханде равно 4.
• 
  Хроматический индекс графа Шрикханде равен 6.
• 
  Граф Шрикханде, нарисованный симметрично.
• 
  Граф Шрикханде гамильтонов.

Примечания

Литература

Ссылки

• The Shrikhande Graph, Peter Cameron, August 2010.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.