Starkt vanligt diagram - Strongly regular graph

Den Paley graf av ordning 13, en starkt regelbunden graf med parametrar srg (13,6,2,3).

I grafteori definieras en starkt regelbunden graf enligt följande. Låt G = ( V , E ) vara ett vanligt diagram med v- hörn och grad k . G sägs vara starkt regelbunden om det också finns heltal λ och μ så att:

Varannan av intilliggande hörn har λ gemensamma grannar.
Varannan icke-intilliggande hörn har μ gemensamma grannar.

En graf av detta slag sägs ibland vara en srg ( v , k , λ, μ). Starkt regelbundna diagram introducerades av RC Bose 1963.

Vissa författare utesluter kurvor som tillfredsställer definitionen trivialt, nämligen de grafer som är den ojämna sammansättningen av en eller flera lika stora hela grafer , och deras kompletteringar , de fullständiga multipartdiagrammen med lika stora oberoende uppsättningar.

Den komplementet av en srg ( v , k , λ, μ) är också starkt regelbundna. Det är en srg ( v , v − k −1, v −2−2 k + μ, v −2 k + λ).

Ett starkt regelbundet diagram är ett avståndsregelbundet diagram med diameter 2 när μ inte är noll. Det är en lokalt linjär graf när λ = 1.

Egenskaper

Förhållandet mellan parametrar

De fyra parametrarna i en srg ( v , k , λ, μ) är inte oberoende och måste följa följande förhållande:

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

Ovanstående relation kan härledas mycket enkelt genom ett räknarargument enligt följande:

Föreställ dig att kurvorna i diagrammet ligger i tre nivåer. Välj vilken topp som helst som rot, i nivå 0. Sedan ligger dess k grannar i nivå 1 och alla andra toppar ligger i nivå 2.
Hörn i nivå 1 är direkt kopplade till roten, därför måste de ha λ andra grannar gemensamt med roten, och dessa vanliga grannar måste också vara i nivå 1. Eftersom varje toppunkt har grad k finns det kvar kanter för varje nivå 1 för att ansluta till noder i nivå 2. Därför finns det kanter mellan nivå 1 och nivå 2. ${\ displaystyle k- \ lambda -1}$ ${\ displaystyle k \ times (k- \ lambda -1)}$
Vertices i nivå 2 är inte direkt kopplade till roten, därför måste de ha μ gemensamma grannar med roten, och dessa vanliga grannar måste alla vara i nivå 1. Det finns toppar i nivå 2, och var och en är ansluten till μ-noder i nivå 1. Därför är antalet kanter mellan nivå 1 och nivå 2 . ${\ displaystyle (vk-1)}$ ${\ displaystyle (vk-1) \ times \ mu}$
Jämförelsen av de två uttrycken för kanterna mellan nivå 1 och nivå 2 följer förhållandet.

Adjacency matris

Låt jag beteckna identitetsmatrisen och låta J beteckna matrisen för en , båda matriserna för ordning v . Den grannmatris A av ett starkt regelbundna graf uppfyller två ekvationer. Först:

{\ displaystyle AJ = JA = kJ,}

vilket är en trivial omformulering av regelbundenhetskravet. Detta visar att k är en egenvärde för angränsningsmatrisen med all-ens egenvektor. För det andra är en kvadratisk ekvation,

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

vilket uttrycker stark regelbundenhet. Den ij : de elementet i den vänstra sidan ger antalet två steg banor från i till j . Den första termen i RHS ger antalet självvägar från i till i , nämligen k kanter ut och tillbaka in. Den andra termen ger antalet tvåstegsvägar när i och j är direkt anslutna. Den tredje termen ger motsvarande värde när i och j inte är anslutna. Eftersom de tre fallen är ömsesidigt uteslutande och kollektivt uttömmande följer den enkla additiva jämställdheten.

Omvänt är ett diagram vars angränsningsmatris uppfyller båda ovanstående villkor och som inte är en fullständig eller noll graf är ett mycket vanligt diagram.

Eigenvärden

Adaptensmatrisen i diagrammet har exakt tre egenvärden :

k , vars mångfald är 1 (som visas ovan)
${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) + {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ ,\rätt],}$ vars mångfald är ${\ displaystyle {\ frac {1} {2}} \ left [(v-1) - {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu ) ^ {2} +4 (k- \ mu)}}} \ höger]}$
${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) - {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ ,\rätt],}$ vars mångfald är ${\ displaystyle {\ frac {1} {2}} \ left [(v-1) + {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu ) ^ {2} +4 (k- \ mu)}}} \ höger]}$

Eftersom mångfalden måste vara heltal ger deras uttryck ytterligare begränsningar för värdena v , k , μ och λ , relaterade till de så kallade Kerin-förhållandena .

Starkt vanliga grafer för vilka har heltal egenvärden med olika multiplikationer. ${\ displaystyle 2k + (v-1) (\ lambda - \ mu) \ neq 0}$

Starkt vanliga diagram för vilka kallas konferensdiagram på grund av deras samband med symmetriska konferensmatriser . Deras parametrar minskar till ${\ 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)}.}

Omvänt är en ansluten vanlig graf med endast tre egenvärden starkt regelbunden.

Exempel

Den cykel med längd 5 är en srg (5, 2, 0, 1).
Den Petersen grafen är en srg (10, 3, 0, 1).
Den Clebsch graf är en srg (16, 5, 0, 2).
Den Shrikhande graf är en srg (16, 6, 2, 2) som inte är en avstånd-transitiv graf .
Den n × n fyrkantiga tåringens graf , dvs. linjediagrammet för en balanserad fullständig bipartitgraf K _{n, n} , är en srg ( n ² , 2 n - 2, n - 2, 2). Parametrarna för n = 4 sammanfaller med dem i Shrikhande-grafen, men de två graferna är inte isomorfa.
Den linjegraf av en fullständig graf K _n är ett srg ( ). ${\ displaystyle {\ binom {n} {2}}, 2 (n-2), n-2,4}$
De Chang grafer är srg (28, 12, 6, 4), samma som linjediagrammet av K ₈ , men dessa fyra grafer inte är isomorfa.
Den linjegraf av en generaliserad fyrhörning GQ (2, 4) är en srg (27, 10, 1, 5). I själva verket ger varje generaliserad fyrkant av ordning (s, t) ett starkt regelbundet diagram på detta sätt: till exempel en srg ((s + 1) (st + 1), s (t + 1), s-1, t +1).
Den Schläfli graf är en srg (27, 16, 10, 8).
Den Hoffman-Singleton graf är en srg (50, 7, 0, 1).
Den Sims-Gewirtz graf är en (56, 10, 0, 2).
Den M22 graf aka Mesner graf är en srg (77, 16, 0, 4).
Den Brouwer-Haemers graf är en srg (81, 20, 1, 6).
Den Higman-Sims graf är en srg (100, 22, 0, 6).
Den lokala McLaughlin-grafen är en srg (162, 56, 10, 24).
Den Cameron graf är en srg (231, 30, 9, 3).
Den Berlekamp-van Lint-Seidel graf är en srg (243, 22, 1, 2).
Den McLaughlin graf är en srg (275, 112, 30, 56).
Den Paley graf av ordning q är ett srg ( q , ( q - 1) / 2, ( q - 5) / 4, ( q - 1) / 4). Den minsta Paley-grafen, med q = 5, är 5-cykeln (ovan).
självkomplementära bågtransitiva diagram är starkt regelbundna.

En starkt regelbunden graf kallas primitiv om både grafen och dess komplement är kopplade. Alla ovanstående diagram är primitiva, eftersom annars μ = 0 eller λ = k.

Conways 99-grafproblem ber om konstruktion av en srg (99, 14, 1, 2). Det är okänt om det finns en graf med dessa parametrar och John Horton Conway har erbjudit ett $ 1000-pris för lösningen på detta problem.

Triangelfria grafer, Moore-grafer och geodetiska grafer

De starkt regelbundna graferna med λ = 0 är triangelfria . Bortsett från de kompletta graferna på färre än 3 hörn och alla kompletta tvåpartsdiagram är de sju ovan (pentagon, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22 och Higman-Sims) de enda kända. Starkt regelbundna diagram med λ = 0 och μ = 1 är Moore-diagram med omkrets 5. Återigen de tre graferna ovan (pentagon, Petersen och Hoffman-Singleton), med parametrar (5, 2, 0, 1), (10, 3, 0, 1) och (50, 7, 0, 1), är de enda kända. Den enda andra möjliga uppsättningen parametrar som ger ett Moore-diagram är (3250, 57, 0, 1); det är okänt om en sådan graf finns, och i så fall om den är unik eller inte.

Mer allmänt är varje starkt regelbunden graf med en geodetisk graf , en graf där varannan hörn har en unik, obeviktad kortaste väg . De enda kända starka regelbundna graferna med är Moore-graferna. Det är inte möjligt för en sådan graf att ha , men andra kombinationer av parametrar som (400, 21, 2, 1) har ännu inte uteslutits. Trots pågående forskning om de egenskaper som en mycket regelbunden graf med skulle ha är det inte känt om det finns mer eller till och med om antalet är begränsat. ${\ displaystyle \ mu = 1}$ ${\ displaystyle \ mu = 1}$ ${\ displaystyle \ lambda = 1}$ ${\ displaystyle \ mu = 1}$

Se även

Anteckningar

Referenser

AE Brouwer, AM Cohen och A. Neumaier (1989), Distansregelbundna diagram . Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5 , ISBN 0-387-50619-5
Chris Godsil och Gordon Royle (2004), algebraisk grafteori . New York: Springer-Verlag. ISBN 0-387-95241-1

Graffamiljer definierade av deras automorfismer
avståndstransitiv	→	avstånd-regelbunden	←	starkt regelbunden
↓
symmetrisk (bågtransitiv)	←	t -transitiv, $t \geq 2$		skev-symmetrisk
↓
_{(om ansluten)} vertex- och edge-transitive	→	kanttransitiv och regelbunden	→	kantövergående
↓		↓		↓
vertex-transitive	→	regelbunden	→	_{(om bipartit)} dubbelreglert
↑
Cayley-diagram	←	noll-symmetrisk		asymmetrisk

Languages

In other projects