Silně pravidelný graf

V teorii grafů je silně pravidelný graf graf, který má následující vlastnosti:

Dovolit být pravidelný graf s vrcholy a stupněm . Říká se, že je silně pravidelné , pokud existují celá čísla a taková, že: $G=(V,E)$ $proti$ $k$ $G$ $\lambda$ $\mu$

Jakékoli dva sousední vrcholy mají společné sousedy. $\lambda$

Jakékoli dva nesousedící vrcholy mají společné sousedy. $\mu$

Grafy tohoto druhu se někdy označují jako . $srg(v,k,\lambda ,\mu )$

Někteří autoři vylučují grafy splňující podmínky triviálně, konkrétně grafy, které jsou disjunktním spojením jednoho nebo více úplných grafů stejné velikosti [1] [2] , a jejich doplňky , Turanovy grafy .

Silně pravidelný graf je vzdálenostně pravidelný s průměrem , ale pouze pokud je nenulový. $2$ $\mu$

Vlastnosti

Čtyři parametry v nejsou nezávislé a musí splňovat následující podmínku: $srg(v,k,\lambda ,\mu )$

(vk-1)\mu =k(k-\lambda -1)

Tuto podmínku lze získat velmi jednoduše spočítáním argumentů takto:

Představte si, že vrcholy grafu leží na třech úrovních. Zvolme libovolný vrchol jako kořen, úroveň . Potom jeho sousední vrcholy leží na úrovni a všechny zbývající vrcholy leží na úrovni . $0$ $k$ $jeden$ $2$
Vrcholy úrovně jsou spojeny přímo s kořenem, a proto musí mít další sousedy, kteří jsou sousedy kořene, a tito sousedé musí také ležet na úrovni . Protože každý vrchol má stupeň , existují hrany spojující každý vrchol úrovně s úrovní . $jeden$ $\lambda$ $jeden$ $k$ $k-\lambda-1$ $jeden$ $2$
Vrcholy úrovně nejsou přímo spojeny s kořenem, a proto musí mít společné sousedy s kořenem a všichni tito sousedé musí ležet na úrovni . To znamená, že vrcholy úrovně jsou připojeny ke každému vrcholu úrovně a každý z vrcholů úrovně 1 je připojen k vrcholům úrovně . Dostaneme, že počet vrcholů v úrovni je roven . $2$ $\mu$ $jeden$ $\mu$ $jeden$ $2$ $k$ $k-\lambda-1$ $2$ $2$ $k(k-\lambda -1)/\mu$
Celkový počet vrcholů na všech třech úrovních je tedy stejný a po transformaci dostaneme . $v=1+k+k(k-\lambda -1)/\mu$ $(vk-1)\mu =k(k-\lambda -1)$

Označme matici identity (řádu ) a nechť označme matici, jejíž všechny prvky jsou rovny . Matice sousedství silně regulárního grafu má následující vlastnosti: $\mathbf {I}$ $proti$ $\mathbf {J}$ $jeden$ ${\mathbf A}$
- $\mathbf {A} \mathbf {J} =k\mathbf {J}$
  (Toto je triviální parafráze požadavku, aby se stupeň vrcholů rovnal ). $k$
- ${\mathbf {A} }^{2}+(\mu -\lambda ){\mathbf {A} }+(\mu -k){\mathbf {I} }=\mu {\mathbf { J} }$
  (První člen, , udává počet dvouskokových cest z libovolného vrcholu ke všem vrcholům. Druhý člen, , odpovídá přímo spojeným hranám. Třetí člen, , odpovídá triviálním párům, když jsou vrcholy v páru stejné ). ${\displaystyle {\mathbf {A} }^{2))$ ${\displaystyle (\mu -\lambda ){\mathbf {A} ))$ $(\mu -k){\mathbf {I} }$

Graf má přesně tři vlastní čísla :
- $k$ , jehož násobek se rovná 1
- ${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )))\ že jo]$ , jehož násobnost se rovná ${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
- ${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )))\ že jo]$ , jehož násobnost se rovná ${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$

Silně regulární grafy, pro které se nazývají konferenční grafy kvůli jejich spojení se symetrickými konferenčními maticemi . Počet nezávislých parametrů těchto grafů je snížen na jeden - . $2k+(v-1)(\lambda -\mu )=0$ $srg\left(v,{\frac {v-1}{2)),{\frac {v-5}{4)),{\frac {v-1}{4))\right)$

Silně pravidelné grafy, pro které mají vlastní čísla celá čísla s nestejnými násobnostmi. $2k+(v-1)(\lambda -\mu )\neq 0$

Přídavek je také silně pravidelný - je . $srg(v,k,\lambda ,\mu )$ $srg(v,vk-1,v-2-2k+\mu ,v-2k+\lambda )$

Příklady

$srg(5,2,0,1)$ — Cyklus délky 5;
$srg(10,3,0,1)$ - hrabě Petersen ;
$srg(16,5,0,2)$ - hrabě Clebsha ;
$srg(16,6,2,2)$ — hrabě Shrikhande , který není vzdálenostně tranzitivní ;
$srg(27,10,1,5)$ - Spojnicový graf zobecněného čtyřúhelníku ; $GQ(2,4)$
$srg(27,16,10,8)$ - hrabě Schläfli [3] ;
$srg(28,12,6,4)$ — Hrabat z Chan ;
$srg(50,7,0,1)$ — hrabě z Hoffman-Singleton ;
$srg(56,10,0,2)$ - hrabě Gewirtz ;
$srg(77,16,0,4)$ - Počet M22 ;
$srg(81,20,1,6)$ - hrabě Brouwer - Hemers ;
$srg(100,22,0,6)$ - Hrabě Higman - Sims ;
$srg(162,56,10,24)$ — Local McLaughlin graph ;
$srg(q,{\frac {q-1}{2)),{\frac {q-5}{4)),{\frac {q-1}{4))))$ — Řád hraběte z Paley ; $q$
$srg(n^{2},2n-2,n-2,2)$ je čtvercový věžový graf . $n\krát n$

O silně regulárním grafu se říká , že je jednoduchý , pokud jsou graf i jeho doplněk propojeny. Všechny výše uvedené grafy jsou jednoduché, protože jinak nebo . $\mu=0$ $\mu=k$

Counts of Moore

Silně pravidelné grafy s neobsahují trojúhelníky . Kromě úplných grafů s méně než 3 vrcholy a všech úplných bipartitních grafů je všech výše uvedených sedm známých grafů tohoto typu. Silně pravidelné grafy s a jsou Mooreovy grafy s obvodem 5. Opět platí, že tři výše uvedené grafy s parametry a jsou jediné známé grafy tohoto druhu. Jediná další možná sada parametrů odpovídající Moorovým grafům je . Není známo, zda takový graf existuje, a pokud ano, zda je jedinečný. $\lambda =0$ $\lambda =0$ $\mu=1$ $srg(5,2,0,1)$ $srg(10,3,0,1)$ $srg(50,7,0,1)$ $srg(3250,57,0,1)$

Viz také

Matice sousedství Seidel

Poznámky

↑ Brouwer, 2012 , str. 101.
↑ Godsil, 2001 , str. 218.
↑ Weisstein, Eric W. Schläfli graf (anglicky) na webu Wolfram MathWorld .

Literatura

Brouwer AE, Cohen AM, Neumaier A. Distance Regular Graphs . - Berlín, New York: Springer-Verlag, 1989. - ISBN 3-540-50619-5 .
Brouwer A.E., Haemers W.H. Spectra of Graphs (anglicky) . - New York: Springer-Verlag, 2012. - Sv. 418.- (Universitex). — ISBN 978-1-4614-1938-9 .
Godsil C., Royle G. Teorie algebraických grafů (anglicky) . - New York: Springer-Verlag, 2001. - ISBN 0-387-95241-1 .

Odkazy

Eric W. Weisstein , článek Mathworld s mnoha příklady.
Gordon Royle , Seznam velkých grafů a rodin.
Andries E. Brouwer , Parametry silně regulárních grafů.
Brendan McKay , Graph Collection.
Ted Spence, Silně pravidelné grafy na maximálně 64 vrcholech.