Avstands-vanlig graf - Distance-regular graph

I matematikk er en avstandsregelmessig graf en vanlig graf slik at antall to hjørner på avstand j fra v og på avstand k fra w for alle to hjørner v og w bare avhenger av j , k og i = d (v , w) .

Hver avstandstransitive graf er avstandsregelmessig. Faktisk ble avstandsregelmessige grafer introdusert som en kombinatorisk generalisering av avstandstransitive grafer, med de numeriske regelmessighetsegenskapene til sistnevnte uten nødvendigvis å ha en stor automorfisme-gruppe .

Kryssarrayer

Det viser seg at en grafisk fremstilling av diameter er avstand-regulær hvis og bare hvis det er en rekke hele tall , slik at for alle , angir hvor mange naboer av på avstand fra og gir antallet naboer av på avstand fra for noen par hjørner og på avstand på . Matrisen av heltall som kjennetegner en avstandsregelmessig graf, er kjent som skjæringsoppsettet . ${\ displaystyle G}$${\ displaystyle d}$${\ displaystyle \ {b_ {0}, b_ {1}, \ ldots, b_ {d-1}; c_ {1}, \ ldots, c_ {d} \}}$${\ displaystyle 1 \ leq j \ leq d}$${\ displaystyle b_ {j}}$${\ displaystyle u}$${\ displaystyle j + 1}$${\ displaystyle v}$${\ displaystyle c_ {j}}$${\ displaystyle u}$${\ displaystyle j-1}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle j}$${\ displaystyle G}$

Cospectral avstandsregelmessige grafer

Et par tilkoblede avstandsregelmessige grafer er cospektrale hvis og bare hvis de har samme skjæringsoppsett.

En avstandsregelmessig graf kobles fra hvis og bare hvis den er en usammenhengende forening av cospektrale avstandsregelmessige grafer.

Eiendommer

Anta at det er en tilkoblet avstandsregelmessig graf for valens med skjæringsoppsett . For alle : la betegne den -regelmessige grafen med tilknytningsmatrise dannet ved å relatere toppunktpar på avstand , og la angi antall naboer på avstand fra for et par toppunkt og på avstand på . ${\ displaystyle G}$ ${\ displaystyle k}$${\ displaystyle \ {b_ {0}, b_ {1}, \ ldots, b_ {d-1}; c_ {1}, \ ldots, c_ {d} \}}$${\ displaystyle 0 \ leq j \ leq d}$${\ displaystyle G_ {j}}$${\ displaystyle k_ {j}}$ ${\ displaystyle A_ {j}}$${\ displaystyle G}$${\ displaystyle j}$${\ displaystyle a_ {j}}$${\ displaystyle u}$${\ displaystyle j}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle j}$${\ displaystyle G}$

Grafteoretiske egenskaper

• ${\ displaystyle {\ frac {k_ {j + 1}} {k_ {j}}} = {\ frac {b_ {j}} {c_ {j + 1}}}}$ for alle . ${\ displaystyle 0 \ leq j <d}$
• ${\ displaystyle b_ {0}> b_ {1} \ geq \ cdots \ geq b_ {d-1}> 0}$ og . ${\ displaystyle 1 = c_ {1} \ leq \ cdots \ leq c_ {d} \ leq b_ {0}}$

Spektrale egenskaper

• ${\ displaystyle k \ leq {\ frac {1} {2}} (m-1) (m + 2)}$ for en hvilken som helst egenverdimultiplikasjon av , med mindre det er en komplett graf for flere partier. ${\ displaystyle m> 1}$${\ displaystyle G}$${\ displaystyle G}$
• ${\ displaystyle d \ leq 3m-4}$ for hvilken som helst egenverdimultiplikasjon av , med mindre det er en syklusgraf eller en komplett graf for flere partier. ${\ displaystyle m> 1}$${\ displaystyle G}$${\ displaystyle G}$
• ${\ displaystyle \ lambda \ in \ {\ pm k \}}$ hvis er en enkel egenverdi av . ${\ displaystyle \ lambda}$${\ displaystyle G}$
• ${\ displaystyle G}$ har forskjellige egenverdier. ${\ displaystyle d + 1}$

Hvis er sterkt vanlig , da og . ${\ displaystyle G}$${\ displaystyle n \ leq 4m-1}$${\ displaystyle k \ leq 2m-1}$

Eksempler

Graden 7 Klein-grafen og tilhørende kart innebygd i en orienterbar overflate av slekten 3. Denne grafen er avstandsregulert med skjæringsoppsett {7,4,1; 1,2,7} og automorfisme-gruppen PGL (2,7).

Noen første eksempler på avstandsregelmessige grafer inkluderer:

• De komplette grafene .
• De sykluser grafer .
• De rare grafene .
• Den Moore grafer .
• Kollinearitetsgrafen til en vanlig nær polygon .
• Den Wells graf og Sylvester grafen .
• Sterkt vanlige grafer med diameter . ${\ displaystyle 2}$

Klassifisering av avstandsregelmessige grafer

Det er bare endelig mange distinkte avstandsregelmessige grafer av en hvilken som helst valens . ${\ displaystyle k> 2}$

På samme måte er det bare endelig mange forskjellige sammenhengende avstandsregelmessige grafer med en gitt egenverdimultiplikitet (med unntak av de komplette flerdeltagrafene). ${\ displaystyle m> 2}$

Kubiske avstandsregelmessige grafer

De kubiske avstandsregelmessige grafene er fullstendig klassifisert.

De 13 forskjellige kubiske avstandsregelmessige grafer er K ₄ (eller tetrahedral graf ), K _3,3 , Petersen-grafen , den kubiske grafen , Heawood-grafen , Pappus-grafen , Coxeter-grafen , Tutte-Coxeter-grafen , Dodekahedralen graf , Desargues-grafen , Tutte 12-bur , Biggs-Smith-grafen og Foster-grafen .

Referanser

Videre lesning

• Godsil, C. D. (1993). Algebraisk kombinatorikk . Chapman and Hall Mathematics Series. New York: Chapman og Hall. s. xvi + 362. ISBN   978-0-412-04131-0 . MR   1220704 .