Wykres McKaya – Millera – Širáňa

W teorii grafów grafy McKaya – Millera – Širáňa są nieskończoną klasą grafów przechodnich wierzchołków o średnicy dwa iz dużą liczbą wierzchołków w stosunku do ich średnicy i stopnia . Zostały nazwane na cześć Brendana McKaya , Mirki Millera i Jozefa Širáňa, którzy jako pierwsi skonstruowali je za pomocą wykresów napięcia w 1998 roku.

Tło

Kontekstem konstrukcji tych wykresów jest problem stopnia średnicy w teorii grafów , który szuka największego możliwego wykresu dla każdej kombinacji stopnia i średnicy. W przypadku wykresów o średnicy dwa każdy wierzchołek można osiągnąć w dwóch krokach od dowolnego wierzchołka $wierzchołki$ , a jeśli stopień wynosi, $co$ najwyżej można osiągnąć w jednym kroku, a drugim ${\ Displaystyle d (d-1)}$ w dwóch krokach, dając Moore związał , że całkowita liczba wierzchołków może wynosić co najwyżej ${\ Displaystyle d ^ {2} + 1}$ . Jednak znane są tylko cztery grafy, które osiągają tę granicę: pojedyncza krawędź (stopień pierwszy), wykres cyklu z 5 wierzchołkami (stopień drugi), wykres Petersena (stopień trzeci) i wykres Hoffmana – Singletona (stopień siódmy). Jeszcze tylko jeden z tych wykresów Moore'a może istnieć ze stopniem 57. Dla wszystkich innych stopni maksymalna liczba wierzchołków w grafie o średnicy dwa musi być mniejsza. Do czasu konstrukcji grafów McKaya – Millera – Širáňa jedyna znana konstrukcja osiągała liczbę wierzchołków równą

${\ Displaystyle \ lewo \ lfloor {\ Frac {d + 2} {2}} \ prawo \ rfloor \ cdot \ lewo \ lceil {\ Frac {d + 2 }{2}}\prawo\rceil ,}$

przy użyciu konstrukcji grafu Cayleya .

Zamiast tego grafy McKay – Miller – Širáň mają liczbę wierzchołków równą

${\ Displaystyle {\ Frac {8} {9}} \ lewo (d + {\ Frac {1} {2}} \ prawo) ^ {2},}$

dla nieskończenie wielu wartości ${\ displaystyle d}$ . Stopnie, $budowlane$ to te, dla których ${\ Displaystyle (2d + 1) / 3}$ jest potęgą pierwszą i jest przystający do 1 modulo 4 . Te możliwe stopnie to liczby

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

Pierwsza liczba w tej sekwencji, 7, to stopień wykresu Hoffmana – Singletona, a wykres McKaya – Millera – Širáňa stopnia siódmego to wykres Hoffmana – Singletona. Tę samą konstrukcję można również zastosować do stopni, $Displaystyle$ których $(2d + 1) / 3}$ jest potęgą pierwszą, ale wynosi 0 lub -1 mod 4. W w takich przypadkach nadal tworzy wykres z tymi samymi wzorami na jego rozmiar, średnicę i stopień, ale te wykresy generalnie nie są przechodnie przez wierzchołek.

Po zbudowaniu grafów McKaya – Millera – Širáňa, inne grafy z jeszcze większą liczbą wierzchołków, mniej niż granica Moore'a, ${\ Displaystyle O (d ^ {3/2})}$ zostały zbudowane. Jednak obejmują one znacznie bardziej ograniczony zestaw stopni niż wykresy McKaya – Millera – Širáňa.

Konstrukcje

Oryginalna konstrukcja McKaya, Millera i Širáňa wykorzystywała $wykresów$ ich jako pokrywającego wykres , gdzie $1)/3}$ ( 2d + jest potęgą pierwszą i gdzie ${\ Displaystyle K_ {q, q} ^ {*}}$ wykres dwudzielny ${\ Displaystyle K_ {q, q}}$ przez dołączenie samopętli do każdego wierzchołka ${\ Displaystyle (q-1)/4} .$ Zamiast tego Šiagiová (2001) ponownie wykorzystuje metodę wykresu napięcia, ale zastosowaną do prostszego wykresu, wykresu dipolowego z $równoległymi krawędziami zmodyfikowanymi w ten sam$ , dołączając tę ​​samą liczbę pętli własnych do każdego wierzchołka.

Możliwe jest również skonstruowanie wykresów McKaya – Millera – Širáňa poprzez $wykresu$ Leviego płaszczyzny afinicznej nad polem porządku .

Dodatkowe właściwości

Widmo wykresu McKaya – Millera – Širáňa ma co najwyżej pięć różnych wartości własnych. Na niektórych z tych wykresów wszystkie te wartości są liczbami całkowitymi, więc wykres jest wykresem całkowym .