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

Граф Шрікханде
Названо на честь	Ш. Ш. Шрікханде
Вершин	16
Ребер	48
Радіус	2
Діаметр	2
Обхват	3
Автоморфізм	192
Хроматичне число	4
Хроматичний індекс	6
Число черг	3
Властивості	сильно регулярний гамільтонів симетричний ейлерів цілий

Граф Шрікханде — граф, знайдений Ш. Ш. Шрікханде^[en] 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-вимірним кістяком тріангуляції Вітні деякої поверхні. У разі графа Шрікханде ця поверхня — тор, у якому кожна вершина оточена шістьма трикутниками. Таким чином, граф Шрікханде — це тороїдальний граф. Вкладення утворює регулярне відображення в тор з 32 трикутними гранями. Кістяк дуального графа цього відображення (як вкладеного в тор) — граф Діка, кубічний симетричний граф.

Граф Шрікханде не є дистанційно-транзитивним. Це найменший дистанційно-регулярний граф, який не є дистанційно-транзитивним^[4].

Група автоморфізмів графа Шрікханде має порядок 192. Вона діє транзитивно на вершини, на ребра та дуги графа. Тому граф Шрікханде є симетричним графом.

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

Граф має книжкову товщину 4 та число черг 3 ^[5].

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

• Графи Чана

• The Shrikhande Graph Пітер Кемерон (Peter Cameron), серпень 2010. Архівовано листопад 24, 2010 на сайті Wayback Machine.