Grafic puternic regulat

În teoria grafurilor, un graf puternic regulat este un graf care are următoarele proprietăți:

Fie un grafic regulat cu vârfuri și grad . Se spune că este puternic regulat dacă există numere întregi și astfel încât: $G=(V,E)$ $v$ $k$ $G$ $\lambda$ $\mu$

Orice două vârfuri adiacente au vecini comuni. $\lambda$

Orice două vârfuri neadiacente au vecini comuni. $\mu$

Graficele de acest fel sunt uneori notate ca . $srg(v,k,\lambda,\mu)$

Unii autori exclud grafurile care îndeplinesc condițiile în mod trivial, și anume grafurile care sunt o uniune disjunctă a unuia sau mai multor grafuri complete de aceeași dimensiune [1] [2] , și complementele lor , grafuri Turan .

Un grafic puternic regulat este distanță-regular cu diametrul , dar numai dacă este diferit de zero. $2$ $\mu$

Proprietăți

Cei patru parametri din nu sunt independenți și trebuie să îndeplinească următoarea condiție: $srg(v,k,\lambda,\mu)$

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

Această condiție poate fi obținută foarte simplu prin numărarea argumentelor după cum urmează:

Imaginează-ți vârfurile graficului situate pe trei niveluri. Să alegem orice vârf ca rădăcină, nivel . Apoi vârfurile învecinate se află la nivel , iar toate vârfurile rămase se află la nivel . $0$ $k$ $unu$ $2$
Vârfurile nivelului sunt conectate direct la rădăcină și, prin urmare, trebuie să aibă alți vecini care sunt vecini cu rădăcina, iar acești vecini trebuie să se afle, de asemenea, pe nivel . Deoarece fiecare vârf are un grad , există muchii care leagă fiecare vârf de nivel la nivel . $unu$ $\lambda$ $unu$ $k$ $k-\lambda-1$ $unu$ $2$
Vârfurile nivelului nu sunt conectate direct la rădăcină și, prin urmare, trebuie să aibă vecini comuni cu rădăcina, iar toți acești vecini trebuie să se afle pe nivel . Astfel, vârfurile de nivel sunt conectate la fiecare vârf de nivel și fiecare dintre vârfurile de nivel 1 este conectat la vârfurile de nivel . Obținem că numărul de vârfuri din nivel este egal cu . $2$ $\mu$ $unu$ $\mu$ $unu$ $2$ $k$ $k-\lambda-1$ $2$ $2$ $k(k-\lambda -1)/\mu$
Prin urmare, numărul total de vârfuri la toate cele trei niveluri este egal și după transformare, obținem . $v=1+k+k(k-\lambda -1)/\mu$ $(vk-1)\mu =k(k-\lambda -1)$

Să notăm matricea de identitate (de ordin ) și să notăm matricea ale cărei elemente sunt egale cu . Matricea de adiacență a unui grafic puternic regulat are următoarele proprietăți: $\mathbf {I}$ $v$ $\mathbf {J}$ $unu$ ${\mathbf A}$
- $\mathbf {A} \mathbf {J} =k\mathbf {J}$
  (Aceasta este o parafrază trivială a cerinței ca gradul vârfurilor să fie egal cu ). $k$
- ${\mathbf {A} }^{2}+(\mu -\lambda ){\mathbf {A} }+(\mu -k){\mathbf {I} }=\mu {\mathbf { J} }$
  (Primul termen, , oferă numărul de căi cu două salturi de la orice vârf la toate vârfurile. Al doilea termen, , corespunde muchiilor conectate direct. Al treilea termen, , corespunde perechilor triviale când vârfurile din pereche sunt aceleași ). ${\mathbf {A} }^{2)$ $(\mu -\lambda ){\mathbf {A} )$ $(\mu -k){\mathbf {I} }$

Graficul are exact trei valori proprii :
- $k$ , multiplicitatea este egală cu 1
- ${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )))\ dreapta]$ , a cărui multiplicitate este egală cu ${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\dreapta]$
- ${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )))\ dreapta]$ , a cărui multiplicitate este egală cu ${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\dreapta]$

Grafice puternic obișnuite pentru care sunt numite grafice de conferință datorită conexiunii lor cu matrici de conferință simetrice . Numărul de parametri independenți ai acestor grafice este redus la unu - . $2k+(v-1)(\lambda -\mu )=0$ $srg\left(v,{\frac {v-1}{2)),{\frac {v-5}{4)),{\frac {v-1}{4)}\right)$

Grafice puternic regulate pentru care , au valori proprii întregi cu multiplicități inegale. $2k+(v-1)(\lambda -\mu )\neq 0$

Adăugarea este, de asemenea, puternic obișnuită - este . $srg(v,k,\lambda,\mu)$ $srg(v,vk-1,v-2-2k+\mu,v-2k+\lambda)$

Exemple

$srg(5,2,0,1)$ — Ciclul de lungime 5;
$srg(10,3,0,1)$ - Contele Petersen ;
$srg(16,5,0,2)$ - Contele Clebsha ;
$srg(16,6,2,2)$ — Contele Shrikhande , care nu este tranzitiv la distanță ;
$srg(27,10,1,5)$ - Graficul liniilor unui patrulater generalizat ; $GQ(2,4)$
$srg(27,16,10,8)$ - Contele Schläfli [3] ;
$srg(28,12,6,4)$ — Conții de Chan ;
$srg(50,7,0,1)$ — Contele de Hoffman-Singleton ;
$srg(56,10,0,2)$ - Contele Gewirtz ;
$srg(77,16,0,4)$ - Număr M22 ;
$srg(81,20,1,6)$ - Contele Brouwer - Hemers ;
$srg(100,22,0,6)$ - Contele Higman - Sims ;
$srg(162,56,10,24)$ — Graficul local McLaughlin ;
$srg(q,{\frac {q-1}{2)),{\frac {q-5}{4)),{\frac {q-1}{4)}))$ — Ordinul Contelui de Paley ; $q$
$srg(n^{2},2n-2,n-2,2)$ este un grafic cu turn pătrat . $n\ ori n$

Se spune că un grafic puternic regulat este simplu dacă atât graficul, cât și complementul său sunt conectate. Toate graficele de mai sus sunt simple, deoarece altfel sau . $\mu=0$ $\mu=k$

Conții de Moore

Graficele puternic regulate cu nu conțin triunghiuri . În afară de graficele complete cu mai puțin de 3 vârfuri și toate graficele bipartite complete, cele șapte de mai sus sunt toate grafice cunoscute de acest tip. Grafice puternic regulate cu și sunt grafice Moore cu circumferința 5. Din nou, cele trei grafice de mai sus, cu parametrii , și , sunt singurele grafice cunoscute de acest fel. Singurul alt set de parametri posibil corespunzător graficelor Moore este . Nu se știe dacă un astfel de grafic există și, dacă da, dacă este unic. $\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)$

Vezi și

Matricea de adiacență Seidel

Note

↑ Brouwer, 2012 , p. 101.
↑ Godsil, 2001 , p. 218.
↑ Weisstein, Eric W. Schläfli graph (engleză) pe site-ul Wolfram MathWorld .

Literatură

Brouwer AE, Cohen AM, Neumaier A. Grafice regulate de distanță . - Berlin, New York: Springer-Verlag, 1989. - ISBN 3-540-50619-5 .
Brouwer A.E., Haemers W.H. Spectre of Graphs (engleză) . - New York: Springer-Verlag, 2012. - Vol. 418.- (Universitex). — ISBN 978-1-4614-1938-9 .
Godsil C., Royle G. Teoria graficelor algebrice (engleză) . - New York: Springer-Verlag, 2001. - ISBN 0-387-95241-1 .

Link -uri

Eric W. Weisstein , articol Mathworld cu multe exemple.
Gordon Royle , Lista de grafice mari și familii.
Andries E. Brouwer , Parametrii graficelor puternic regulate.
Brendan McKay , Colecția Graph.
Ted Spence, Grafice puternic regulate pe cel mult 64 de vârfuri.