Граф Маккея – Миллера – Ширая - McKay–Miller–Širáň graph

В теория графов, то Графы Маккея – Миллера – Ширая бесконечный класс вершинно-транзитивные графы с диаметр два, причем с большим числом вершин относительно их диаметра и степень. Они названы в честь Брендан МакКей, Мирка Миллер, и Йозеф Ширань, который первым построил их, используя графики напряжения в 1998 г.^[1]

Фон

Контекст для построения этих графов - это проблема диаметра градусов в теория графов, который ищет максимально возможный график для каждой комбинации степени и диаметра. Для графов диаметра два каждая вершина может быть достигнута за два шага из произвольной начальной вершины, и если степень равна ${ displaystyle d}$ то самое большее ${ displaystyle d}$ вершины могут быть достигнуты за один шаг и за другой ${ displaystyle d (d-1)}$ в два этапа, давая Мур связан что общее количество вершин может быть не более ${ displaystyle d ^ {2} +1}$. Однако известно, что только четыре графа достигают этой границы: одно ребро (степень один), 5-вершина график цикла (степень два), Граф Петерсена (третья степень), а Граф Хоффмана – Синглтона (степень семь). Только один из них Графики Мура может существовать со степенью 57. Для всех остальных степеней максимальное количество вершин в графе диаметра два должно быть меньше. До построения графов Маккея – Миллера – Ширая единственная известная конструкция достигала числа вершин, равного

${ displaystyle left lfloor { frac {d + 2} {2}} right rfloor cdot left lceil { frac {d + 2} {2}} right rceil,}$

используя Граф Кэли строительство.^[2]

Графы Маккея – Миллера – Ширая вместо этого имеют число вершин, равное

${ displaystyle { frac {8} {9}} left (d + { frac {1} {2}} right) ^ {2},}$

для бесконечного множества значений ${ displaystyle d}$. Степени ${ displaystyle d}$ для которых их строительные работы являются теми, для которых ${ displaystyle (2d + 1) / 3}$ это основная сила и является конгруэнтно 1 по модулю 4. Эти возможные степени - это числа

7, 13, 19, 25, 37, 43, 55, 61, 73, 79, 91, ...

Первое число в этой последовательности, 7, представляет собой степень графа Хоффмана – Синглтона, а граф Маккея – Миллера – Ширая степени седьмой - это граф Хоффмана – Синглтона.^[2] Та же конструкция может быть применена к градусам ${ displaystyle d}$ для которого ${ displaystyle (2d + 1) / 3}$ является степенью простого числа, но равна 0 или −1 по модулю 4. В этих случаях он по-прежнему создает граф с теми же формулами для его размера, диаметра и степени, но эти графы в общем случае не являются вершинно-транзитивными.^[1][3]

После построения графов Маккея – Миллера – Ширая другие графы с еще большим числом вершин, ${ displaystyle O (d ^ {3/2})}$ было построено меньше, чем граница Мура.^[4] Однако они покрывают значительно более ограниченный набор степеней, чем графы Маккея – Миллера – Шираня.^[5]

Конструкции

Первоначальная конструкция Маккея, Миллера и Шираня использовала график напряжения способ построить их как покрывающий граф графика ${ displaystyle K_ {q, q} ^ {*}}$, куда ${ displaystyle q = (2d + 1) / 3}$ это основная сила и где ${ displaystyle K_ {q, q} ^ {*}}$ формируется из полный двудольный граф ${ displaystyle K_ {q, q}}$ прикрепив ${ Displaystyle (д-1) / 4}$ зацикливаются на каждой вершине. Шиагиова (2001) снова использует метод графика напряжения, но применительно к более простому графику дипольный график с ${ displaystyle q}$ параллельные ребра модифицируются таким же образом, присоединяя одинаковое количество петель к каждой вершине.^[2]

Также возможно построить графы Маккея – Миллера – Ширая, изменив Граф Леви из аффинная плоскость над поле порядка ${ displaystyle q}$.^[3][5]

Дополнительные свойства

В спектр графа Маккея – Миллера – Ширая имеет не более пяти различных собственных значений. В некоторых из этих графиков все эти значения являются целыми числами, так что график представляет собой интегральный график.^[6]

Рекомендации