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

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

Побудова

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

Властивості

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

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

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

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

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