График Шрикханде

Неориентированный граф имени С.С. Шрикханде

В математической области теории графов граф Шрикханде — это граф, открытый С. С. Шрикханде в 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}, т. е. . Это равенство подразумевает, что граф связан с симметричным BIBD . Граф Шрикханде разделяет эти параметры ровно с одним другим графом, графом ладьи 4×4 , т. е. линейным графом L ( K _4,4 ) полного двудольного графа K _4,4 . Последний граф является единственным линейным графом L ( K _n,n ), для которого параметры строгой регулярности не определяют этот граф однозначно, но являются общими с другим графом, а именно графом Шрикханде (который не является графом ладьи). ^{[2] [3]} ${\displaystyle \lambda =\mu =2}$

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

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

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

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

Он имеет толщину книги 4 и номер очереди 3. ^[6]

Галерея

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

Примечания

1. Вайсштейн, Эрик В. «График Шриханде». Математический мир .
2. Шрикханде, СС (1959), «Уникальность схемы ассоциации L ₂ », Annals of Mathematical Statistics , 30 : 781–798, doi : 10.1214/aoms/1177706207 , JSTOR  2237417.
3. Harary, F. (1972), "Theorem 8.7", Graph Theory (PDF) , Massachusetts: Addison-Wesley, стр. 79, архивировано из оригинала (PDF) 9 ноября 2013 г..
4. Брауэр, график А.Э. Шрикханде.
5. Брауэр, А.Э.; Коэн, AM; Ноймайер, А. (1989), Дистанционно-регулярные графы , Нью-Йорк: Springer-Verlag, стр. 104–105 и 136..
6. Джессика Вольц, Проектирование линейных макетов с помощью SAT . Магистерская работа, Тюбингенский университет, 2018 г.

Ссылки

• Холтон, ДА; Шихан, Дж. (1993), График Петерсена , Cambridge University Press , стр. 270, ISBN 0-521-43594-3.

Внешние ссылки

• График Шрикханде, Питер Кэмерон , август 2010 г.