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

Граф Шрікханде — граф, знайдений Ш. Ш. Шрікханде 1959 року. Граф сильно регулярний, має 16 вершин і 48 ребер і кожна вершина має степінь 6. Кожна пара вузлів має рівно двох спільних сусідів, незалежно від того, пов'язана ця пара ребром чи ні.

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

Побудова

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

Властивості

У графі Шрікханде будь-які дві вершини I і J мають двох різних спільних сусідів (за винятком самих вершин I і J), що виконується незалежно від того, суміжні I і J, чи ні. Іншими словами, граф сильно регулярний та його параметрами є: {16,6,2,2}, тобто $\lambda =\mu =2$. З цієї рівності випливає, що граф асоційований із симетричними зрівноваженими неповними блок-схемами (англ. Balanced Incomplete Block Designs, BIBD). Такі ж параметри має 4×4 туровий граф, тобто реберний граф L(K_4,4) повного двочасткового графа K_4,4. Останній граф є єдиним реберним графом L(K_{n, n}), якого параметри сильної регулярності не визначають єдиним чином, і граф ділить їх з іншим графом, а саме графом Шрікханде (який не є туровим графом).

Граф Шрікханде локально шестикутний. Тобто сусіди кожної вершини утворюють цикл із шести вершин. Як і будь-який локально циклічний граф, граф Шрікханде є 1-вимірним кістяком тріангуляції Вітні деякої поверхні. У разі графа Шрікханде ця поверхня — тор, у якому кожна вершина оточена шістьма трикутниками. Таким чином, граф Шрікханде — це тороїдальний граф. Вкладення утворює регулярне відображення в тор з 32 трикутними гранями. Кістяк дуального графа цього відображення (як вкладеного в тор) — граф Діка, кубічний симетричний граф.

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

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

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

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

Галерея

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

Див. також

• Графи Чана

Література

• Shrikhande S. S. The uniqueness of the L₂ association scheme // Annals of Mathematical Statistics. — 1959. — Т. 30. — С. 781–798. — DOI:10.1214/aoms/1177706207.
• Frank Harary. Graph Theory. — Massachusetts : Addison-Wesley, 1972.
  • Харари Ф. Теория графов. — М. : Мир, 1973.
• , Cambridge University Press, ISBN 0-521-43594-3 {{citation}}: Пропущений або порожній |title= (довідка)
• Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. — New York : Springer-Verlag, 1989. — С. 104–105, 136.
• Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis)

Посилання

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