Grafic puternic regulat - Strongly regular graph

Graficul Paley comenzii 13, un grafic puternic regulate cu parametrii SRG (13,6,2,3).

În teoria graficelor , un grafic puternic regulat este definit după cum urmează. Fie G = ( V , E ) un grafic regulat cu v vârfuri și grad k . Se spune că G este puternic regulat dacă există și numere întregi λ și μ astfel încât:

• La fiecare două vârfuri adiacente au λ vecini comuni.
• La fiecare două vârfuri neadiacente au μ vecini comuni.

Un grafic de acest fel se spune uneori că este un srg ( v , k , λ, μ). Grafice puternic regulate au fost introduse de RC Bose în 1963.

Unii autori exclud graficele care satisfac definiția în mod trivial, și anume acele grafice care sunt unirea disjunctă a unuia sau mai multor grafice complete de dimensiuni egale și complementele lor , graficele multipartite complete cu seturi independente de dimensiuni egale.

Complementul unui SRG ( v , k , λ, μ) este , de asemenea , puternic regulate. Este un srg ( v , v − k −1, v −2−2 k + μ, v −2 k + λ).

Un grafic puternic regulat este un grafic distanță regulat cu diametrul 2 ori de câte ori μ este diferit de zero. Este un grafic liniar local ori de câte ori λ = 1.

Proprietăți

Relația dintre parametri

Cei patru parametri dintr-un srg ( v , k , λ, μ) nu sunt independenți și trebuie să respecte următoarea relație:

${\ displaystyle (vk-1) \ mu = k (k- \ lambda -1)}$

Relația de mai sus poate fi derivată foarte ușor printr-un argument de numărare după cum urmează:

1. Imaginați-vă vârfurile graficului în trei nivele. Alegeți orice vârf ca rădăcină, la nivelul 0. Atunci k vecinii săi se află la nivelul 1, iar toate celelalte vârfuri se află la nivelul 2.
2. Vârfurile de la nivelul 1 sunt conectate direct la rădăcină, deci trebuie să aibă λ alți vecini în comun cu rădăcina, iar acești vecini comuni trebuie să fie și la nivelul 1. Deoarece fiecare vârf are gradul k , rămân margini pentru fiecare nivel 1 nod pentru a vă conecta la noduri la nivelul 2. Prin urmare, există margini între nivelul 1 și nivelul 2.${\ displaystyle k- \ lambda -1}$${\ displaystyle k \ times (k- \ lambda -1)}$
3. Vârfurile de la nivelul 2 nu sunt conectate direct la rădăcină, prin urmare trebuie să aibă μ vecini comuni cu rădăcina și acești vecini comuni trebuie să fie toți la nivelul 1. Există vârfuri la nivelul 2 și fiecare este conectat la μ noduri la nivelul 1. Prin urmare, numărul muchiilor dintre nivelul 1 și nivelul 2 este .${\ displaystyle (vk-1)}$${\ displaystyle (vk-1) \ times \ mu}$
4. Echivalând cele două expresii pentru marginile dintre nivelul 1 și nivelul 2, relația urmează.

Matricea adiacenței

Să am denota matricea identitate și lăsați J denotă matricea celor , ambele matrici de ordin v . Matricea de adiacenta A unui grafic puternic regulat îndeplinește două ecuații. Primul:

${\ displaystyle AJ = JA = kJ,}$

care este o retratare banală a cerinței de regularitate. Aceasta arată că k este o valoare proprie a matricei de adiacență cu vectorul propriu al tuturor. A doua este o ecuație pătratică,

${\ displaystyle {A} ^ {2} = k {I} + \ lambda {A} + \ mu ({JIA})}$

care exprimă o regularitate puternică. Elementul ij -th din partea stângă dă numărul de căi în doi pași de la i la j . Primul termen al RHS dă numărul de căi de sine de la i la i , și anume k margini în afară și înapoi. Al doilea termen dă numărul de căi în doi pași când i și j sunt conectate direct. Al treilea termen dă valoarea corespunzătoare atunci când i și j nu sunt conectate. Deoarece cele trei cazuri se exclud reciproc și sunt exhaustive , urmează simpla egalitate aditivă.

În schimb, un grafic a cărui matrice de adiacență îndeplinește ambele condiții de mai sus și care nu este un grafic complet sau nul este un grafic puternic regulat.

Valori proprii

Matricea de adiacență a graficului are exact trei valori proprii :

• k , a cărui multiplicitate este 1 (așa cum se vede mai sus)
• ${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) + {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ ,\dreapta],}$ a cărui multiplicitate este ${\ displaystyle {\ frac {1} {2}} \ left [(v-1) - {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu ) ^ {2} +4 (k- \ mu)}}} \ right]}$
• ${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) - {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ ,\dreapta],}$ a cărui multiplicitate este ${\ displaystyle {\ frac {1} {2}} \ left [(v-1) + {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu ) ^ {2} +4 (k- \ mu)}}} \ right]}$

Deoarece multiplicitățile trebuie să fie numere întregi, expresiile lor oferă constrângeri suplimentare asupra valorilor lui v , k , μ și λ , legate de așa-numitele condiții Kerin .

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

Grafice puternic regulate pentru care se numesc grafice de conferință datorită conexiunii lor cu matrici de conferință simetrice . Parametrii lor se reduc la ${\ displaystyle 2k + (v-1) (\ lambda - \ mu) = 0}$

${\ displaystyle {\ text {srg}} {\ big (} v, {\ tfrac {1} {2}} (v-1), {\ tfrac {1} {4}} (v-5), { \ tfrac {1} {4}} (v-1) {\ big)}.}$

În schimb, un grafic regulat conectat cu doar trei valori proprii este puternic regulat.

Exemple

• Ciclul de lungime 5 este un SRG (5, 2, 0, 1).
• Graficul Petersen este un SRG (10, 3, 0, 1).
• Graficul Clebsch este un SRG (16, 5, 0, 2).
• Graficul Shrikhande este un SRG (16, 6, 2, 2) , care nu este un grafic distanță tranzitiv .
• Graficul n  ×  n al turnului pătrat , adică graficul liniar al unui grafic bipartit complet echilibrat K _{n, n} , este un srg ( n ² , 2 n  - 2, n  - 2, 2). Parametrii pentru n = 4 coincid cu cei ai graficului Shrikhande, dar cele două grafice nu sunt izomorfe.
• Graficul linie unui complet grafic K _n este un SRG ( ).${\ displaystyle {\ binom {n} {2}}, 2 (n-2), n-2,4}$
• De Graficele Chang sunt SRG (28, 12, 6, 4), la fel ca linia graficului de K ₈ , dar aceste patru grafice nu sunt izomorfe.
• Graficul linie a unui patrulater generalizat GQ (2, 4) este un SRG (27, 10, 1, 5). De fapt, fiecare patrulater generalizat de ordine (s, t) oferă un grafic puternic regulat în acest fel: a wit, un srg ((s + 1) (st + 1), s (t + 1), s-1, t +1).
• Graficul Schläfli este un SRG (27, 16, 10, 8).
• Graficul Hoffman-Singleton este un SRG (50, 7, 0, 1).
• Graficul Sims-Gewirtz este (56, 10, 0, 2).
• Graficul M22 aka MESNER grafic este un SRG (77, 16, 0, 4).
• Graficul Brouwer-Haemers este un SRG (81, 20, 1, 6).
• Graficul Higman-Sims este un SRG (100, 22, 0, 6).
• Graficul McLaughlin Local este un SRG (162, 56, 10, 24).
• Graficul Cameron este un SRG (231, 30, 9, 3).
• Graficul Berlekamp – van Lint – Seidel este un srg (243, 22, 1, 2).
• Graficul McLaughlin este un SRG (275, 112, 30, 56).
• Graficul Paley comenzii q este un SRG ( q , ( q  - 1) / 2, ( q  - 5) / 4, ( q  - 1) / 4). Cel mai mic grafic Paley, cu q = 5, este ciclul 5 (de mai sus).
• graficele auto-complementare arc tranzitive sunt puternic regulate.

Un grafic puternic regulat se numește primitiv dacă atât graficul, cât și complementul său sunt conectate. Toate graficele de mai sus sunt primitive, altfel μ = 0 sau λ = k.

Problema de 99 de grafice a lui Conway cere construirea unui srg (99, 14, 1, 2). Nu se știe dacă există un grafic cu acești parametri și John Horton Conway a oferit un premiu de 1000 USD pentru soluția la această problemă.

Grafice fără triunghi, grafice Moore și grafice geodezice

Graficele puternic regulate cu λ = 0 sunt libere de triunghi . În afară de graficele complete pe mai puțin de 3 vârfuri și toate graficele bipartite complete, cele șapte enumerate mai sus (pentagon, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22 și Higman-Sims) sunt singurele cunoscute. Grafele puternic regulate cu λ = 0 și μ = 1 sunt grafice Moore cu circumferința 5. Din nou cele trei grafice date mai sus (pentagon, Petersen și Hoffman-Singleton), cu parametrii (5, 2, 0, 1), (10, 3, 0, 1) și (50, 7, 0, 1), sunt singurele cunoscute. Singurul alt set posibil de parametri care dau un grafic Moore este (3250, 57, 0, 1); nu se știe dacă există un astfel de grafic și, dacă da, dacă este unic sau nu.

Mai general, fiecare grafic puternic regulat cu este un grafic geodezic , un grafic în care fiecare două vârfuri au o cale unică cea mai scurtă neponderată . Singurele grafice cunoscute puternic regulate sunt graficele Moore. Nu este posibil ca un astfel de grafic să aibă , dar alte combinații de parametri precum (400, 21, 2, 1) nu au fost încă excluse. În ciuda cercetărilor în curs privind proprietățile pe care le-ar avea un grafic puternic regulat , nu se știe dacă mai există sau chiar dacă numărul lor este finit. ${\ displaystyle \ mu = 1}$${\ displaystyle \ mu = 1}$${\ displaystyle \ lambda = 1}$${\ displaystyle \ mu = 1}$

Vezi si

• Geometrie parțială
• Matricea de adiacență Seidel
• Două grafice

Note

Referințe

• AE Brouwer, AM Cohen și A. Neumaier (1989), Distance Regular Graphs . Berlin, New York: Springer-Verlag. ISBN  3-540-50619-5 , ISBN  0-387-50619-5
• Chris Godsil și Gordon Royle (2004), Teoria graficului algebric . New York: Springer-Verlag. ISBN  0-387-95241-1

linkuri externe

• Eric W. Weisstein , articol Mathworld cu numeroase exemple.
• Gordon Royle , Listă de grafice și familii mai mari.
• Andries E. Brouwer , Parametrii graficelor puternic regulate.
• Brendan McKay , Câteva colecții de grafice.
• Ted Spence , grafice puternic regulate pe cel mult 64 de vârfuri.