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

Электромонтаж Ремонт и отделка Укладка напольных покрытий, теплые полы Тепловодоснабжение

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

18.12.2020

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

Построение

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

Свойства

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

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

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

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

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

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

Галерея

  • Граф Шрикханде является тороидальным.

  • Хроматическое число графа Шрикханде равно 4.

  • Хроматический индекс графа Шрикханде равен 6.

  • Граф Шрикханде, нарисованный симметрично.

  • Граф Шрикханде гамильтонов.


Имя:*
E-Mail:
Комментарий: