Distans-regelbunden graf - Distance-regular graph

I matematik är en avståndsregelbunden graf en vanlig graf så att för alla två hörn v och w , antalet hörn på avståndet j från v och på avståndet k från w beror bara på j , k och i = d (v , w) .

Varje distansövergångsdiagram är avståndsregelbunden. I själva verket introducerades avståndsregelbundna grafer som en kombinatorisk generalisering av avståndstransitiva diagram, med de numeriska regelbundenhetsegenskaperna för den senare utan att nödvändigtvis ha en stor automorfismgrupp .

Korsningsarrayer

Det visar sig att ett diagram av diameter är avstånds regelbunden om och endast om det finns en array av heltal sådan att för alla , ger antalet grannar på avstånd från och ger antalet grannar på avstånd från för varje par av hörn och på avstånd på . Matrisen av heltal som kännetecknar en avståndsregelbunden graf är känd som dess korsningsmatris . ${\ 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 distans-regelbundna diagram

Ett par anslutna avståndsregelbundna grafer är cospektrala om och bara om de har samma korsningsmatris.

En distansregelbunden graf kopplas bort om och endast om den är en ojämn sammanslutning av cospektrala distansregelbundna diagram.

Egenskaper

Antag är en ansluten distans-regelbunden graf för valens med korsningsmatris . För alla : låt beteckna det -regelbundna diagrammet med angränsande matris bildad genom att relatera par av hörn på avstånd , och låt beteckna antalet grannar på avstånd från för ett par hörn och på avstånd 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}$

Grafteoretiska egenskaper

• ${\ displaystyle {\ frac {k_ {j + 1}} {k_ {j}}} = {\ frac {b_ {j}} {c_ {j + 1}}}}$ för alla . ${\ displaystyle 0 \ leq j <d}$
• ${\ displaystyle b_ {0}> b_ {1} \ geq \ cdots \ geq b_ {d-1}> 0}$ och . ${\ displaystyle 1 = c_ {1} \ leq \ cdots \ leq c_ {d} \ leq b_ {0}}$

Spektrala egenskaper

• ${\ displaystyle k \ leq {\ frac {1} {2}} (m-1) (m + 2)}$ för valfri mångfald av egenvärden , såvida det inte finns en fullständig multipartdiagram. ${\ displaystyle m> 1}$${\ displaystyle G}$${\ displaystyle G}$
• ${\ displaystyle d \ leq 3m-4}$ för valfri mångfald av egenvärden , såvida inte ett cykeldiagram eller ett komplett graf för flera delar är. ${\ displaystyle m> 1}$${\ displaystyle G}$${\ displaystyle G}$
• ${\ displaystyle \ lambda \ in \ {\ pm k \}}$ om är en enkel egenvärde av . ${\ displaystyle \ lambda}$${\ displaystyle G}$
• ${\ displaystyle G}$ har distinkta egenvärden. ${\ displaystyle d + 1}$

Om är starkt regelbundet , då och . ${\ displaystyle G}$${\ displaystyle n \ leq 4m-1}$${\ displaystyle k \ leq 2m-1}$

Exempel

Graden 7 Klein-graf och tillhörande karta inbäddad i en orienterbar yta av släktet 3. Denna graf är avståndsregelbunden med korsningsuppsättningen {7,4,1; 1,2,7} och automorfismgruppen PGL (2,7).

Några första exempel på distansregelbundna diagram inkluderar:

• De kompletta graferna .
• De cykler grafer .
• De udda graferna .
• Den Moore grafer .
• Kollinearitetsdiagrammet för en vanlig polygon nära .
• Den Wells grafen och Sylvester grafen .
• Starkt regelbundna diametrar . ${\ displaystyle 2}$

Klassificering av avståndsregelbundna diagram

Det finns bara ändligt många distinkta anslutna distansregelbundna grafer av en given valens . ${\ displaystyle k> 2}$

På samma sätt finns det bara ändå många distinkta anslutna distansregelbundna grafer med en given mångfald av egenvärden (med undantag för de kompletta multipartdiagrammen). ${\ displaystyle m> 2}$

Kubiska distansregelbundna diagram

De kubiska avståndsregelbundna graferna har klassificerats fullständigt.

De 13 distinkta kubiska avståndsregelbundna graferna är K ₄ (eller Tetrahedral graf ), K _3,3 , Petersen-grafen , den kubiska grafen , Heawood-grafen , Pappus-grafen , Coxeter-grafen , Tutte-Coxeter-grafen , Dodekahedralen graf , Desargues-grafen , Tutte 12-bur , Biggs-Smith-grafen och Foster-grafen .

Referenser

Vidare läsning

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