McKay – Miller – Širáňův graf - McKay–Miller–Širáň graph

v teorie grafů, McKay – Miller – Širáň grafy jsou nekonečnou třídou vertex-tranzitivní grafy s průměr dva as velkým počtem vrcholů vzhledem k jejich průměru a stupeň. Jsou pojmenovány po Brendan McKay, Mirka Miller a Jozef Širáň, který je nejprve zkonstruoval pomocí grafy napětí v roce 1998.^[1]

Pozadí

Kontext pro konstrukci těchto grafů je problém s průměrem stupně v teorie grafů, který hledá největší možný graf pro každou kombinaci stupně a průměru. U grafů o průměru dva lze každý vrchol dosáhnout ve dvou krocích od libovolného počátečního vrcholu a pokud je stupeň ${ displaystyle d}$ pak maximálně ${ displaystyle d}$ vrcholů lze dosáhnout v jednom a druhém kroku ${ displaystyle d (d-1)}$ ve dvou krocích, přičemž Moore vázán že celkový počet vrcholů může být maximálně ${ displaystyle d ^ {2} +1}$. Jsou však známy pouze čtyři grafy, které dosáhly této hranice: jedna hrana (první stupeň), 5-vrchol graf cyklu (stupeň dva), Petersenův graf (stupeň tři) a Hoffman – Singletonův graf (stupeň sedm). Pouze jeden z nich Mooreovy grafy může existovat se stupněm 57. U všech ostatních stupňů musí být maximální počet vrcholů v grafu o průměru dva menší. Dokud nebude konstrukce grafů McKay – Miller – Širáň, jediná známá konstrukce dosáhne počtu vrcholů rovných

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

používat Cayleyův graf konstrukce.^[2]

Grafy McKay – Miller – Širáň mají místo toho stejný počet vrcholů

${ displaystyle { frac {8} {9}} vlevo (d + { frac {1} {2}} vpravo) ^ {2},}$

pro nekonečně mnoho hodnot ${ displaystyle d}$. Stupně ${ displaystyle d}$ pro něž jsou jejich stavební práce ${ displaystyle (2d + 1) / 3}$ je hlavní síla a je shodné s 1 modulo 4. Tyto možné stupně jsou čísla

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

První číslo v této sekvenci, 7, je stupeň grafu Hoffman-Singleton a graf McKay-Miller-Širáň stupně 7 je graf Hoffman-Singleton.^[2] Stejnou konstrukci lze použít i na stupně ${ displaystyle d}$ pro který ${ displaystyle (2d + 1) / 3}$ je primární síla, ale je 0 nebo −1 mod 4. V těchto případech stále vytváří graf se stejnými vzorci pro svou velikost, průměr a stupeň, ale tyto grafy nejsou obecně vrcholné.^[1][3]

Po konstrukci grafů McKay – Miller – Širáň, dalších grafů s ještě větším počtem vrcholů, ${ displaystyle O (d ^ {3/2})}$ bylo postaveno méně než Moorových.^[4] Ty však pokrývají výrazně omezenější množinu stupňů než grafy McKay – Miller – Širáň.^[5]

Stavby

Původní konstrukce McKay, Miller a Širáň používala graf napětí metoda jejich konstrukce jako krycí graf grafu ${ displaystyle K_ {q, q} ^ {*}}$, kde ${ displaystyle q = (2d + 1) / 3}$ je hlavní síla a kde ${ displaystyle K_ {q, q} ^ {*}}$ je tvořen z a kompletní bipartitní graf ${ displaystyle K_ {q, q}}$ připojením ${ displaystyle (q-1) / 4}$ self-loops to each vertex. Šiagiová (2001) opět používá metodu grafu napětí, ale aplikuje se na jednodušší graf, a dipólový graf s ${ displaystyle q}$ paralelní hrany upravené stejným způsobem připojením stejného počtu smyček ke každému vrcholu.^[2]

Je také možné sestrojit grafy McKay – Miller – Širáň úpravou Leviho graf z afinní letadlo přes pole řádu ${ displaystyle q}$.^[3][5]

Další vlastnosti

The spektrum grafu McKay – Miller – Širáň má nejvýše pět odlišných vlastních čísel. V některých z těchto grafů jsou všechny tyto hodnoty celá čísla, takže graf je integrální graf.^[6]

Reference