Stark regulärer Graph

In der Graphentheorie ist ein stark regulärer Graph ein regulärer Graph mit bestimmten weiteren Eigenschaften. Neben der Eigenschaft eines ${\displaystyle k}$-regulären Graphen, dass alle seine Ecken ${\displaystyle k}$ Nachbarn haben, gibt es für einen stark regulären Graphen zwei weitere ganze Zahlen ${\displaystyle \lambda ,\mu }$, sodass je zwei benachbarte Ecken ${\displaystyle \lambda }$ gemeinsame Nachbarn haben und je zwei nicht benachbarte Ecken ${\displaystyle \mu }$ gemeinsame Nachbarn haben.

Sei ${\displaystyle \Gamma =(V,E)}$ ein endlicher Graph mit Eckenmenge ${\displaystyle V}$ und Kantenmenge ${\displaystyle E}$. Dann heißt ${\displaystyle \Gamma }$ stark regulär, falls es drei ganze Zahlen ${\displaystyle k,\lambda ,\mu }$ gibt, sodass

• jede Ecke genau ${\displaystyle k}$ Nachbarn hat,
• je zwei benachbarte Ecken genau ${\displaystyle \lambda }$ gemeinsame Nachbarn haben und
• je zwei nicht benachbarte Ecken genau ${\displaystyle \mu }$ gemeinsame Nachbarn haben.

Ist ${\displaystyle v=|V|}$ die Anzahl der Ecken von ${\displaystyle \Gamma }$, so nennt man ${\displaystyle \Gamma }$ einen stark regulären Graphen mit Parametern ${\displaystyle (v,k,\lambda ,\mu )}$.

Oft wird für einen stark regulären Graphen zusätzlich verlangt, dass ${\displaystyle \Gamma }$ nicht leer und nicht vollständig ist.^{[1][A 1]} In diesem Fall stimmt die kombinatorische Definition mit der folgenden Definition über die Adjazenzmatrix überein.

Wie die regulären Graphen lassen sich auch die stark regulären Graphen über ihre Adjazenzmatrix charakterisieren: Sei ${\displaystyle \Gamma =(V,E)}$ ein endlicher Graph mit ${\displaystyle v=|V|}$ und Adjazenzmatrix ${\displaystyle A\in \mathbb {R} ^{v\times v}}$. Sei ${\displaystyle j=(1,\ldots ,1)^{\mathrm {T} }\in \mathbb {R} ^{v}}$ der Einsvektor. Dann heißt ${\displaystyle \Gamma }$ ${\displaystyle k}$-regulär, wenn ${\displaystyle j}$ ein Eigenvektor von ${\displaystyle A}$ zum Eigenwert ${\displaystyle k}$ ist. Ist ${\displaystyle \Gamma }$ ein regulärer Graph, so heißt er stark regulär, wenn ${\displaystyle A}$ genau zwei Eigenwerte hat, die zu ${\displaystyle j}$ orthogonale Eigenvektoren besitzen. Diese zwei Eigenwerte werden üblicherweise mit ${\displaystyle r,s}$ und deren Vielfachheiten mit ${\displaystyle f,g}$ bezeichnet.^[2]

• Die Kreisgraphen ${\displaystyle C_{4}}$ und ${\displaystyle C_{5}}$ mit vier und fünf Ecken sind stark regulär mit Parametern ${\displaystyle (4,2,0,2)}$ und ${\displaystyle (5,2,0,1)}$. Bei den Kreisgraphen ${\displaystyle C_{6},C_{7},\dotsc }$ gibt es sowohl nicht benachbarte Ecken mit einem gemeinsamen Nachbarn als auch solche mit gar keinem gemeinsamen Nachbarn; sie sind daher nicht stark regulär.
• Der Petersen-Graph ist stark regulär mit Parametern ${\displaystyle (10,3,0,1)}$.
• Die disjunkte Vereinigung ${\displaystyle aK_{m}}$ von ${\displaystyle a\geq 2}$ vollständigen Graphen ${\displaystyle K_{m}}$ mit ${\displaystyle m\geq 2}$ ist stark regulär. Sie hat Parameter ${\displaystyle (am,m-1,m-2,0)}$.
• Der vollständig multipartite Graph ${\displaystyle K_{a\times m}}$, dessen ${\displaystyle a\geq 2}$ Partitionsklassen alle genau ${\displaystyle m\geq 2}$ Ecken haben, ist stark regulär. Er hat Parameter ${\displaystyle (am,(a-1)m,(a-2)m,(a-1)m)}$.
• Der Komplementgraph eines stark regulären Graphen mit Parametern ${\displaystyle (v,k,\lambda ,\mu )}$ ist stark regulär. Er hat Parameter ${\displaystyle (v,v-k-1,v-2k+\mu -2,v-2k+\lambda )}$.
• Der Line-Graph des vollständigen Graphen ${\displaystyle K_{m}}$ mit ${\displaystyle m\geq 4}$ Ecken ist stark regulär. Er hat Parameter ${\displaystyle ({\tbinom {m}{2}},2(m-2),m-2,4)}$.

In diesem Abschnitt sei ${\displaystyle \Gamma =(V,E)}$ ein stark regulärer Graph mit Parametern ${\displaystyle (v,k,\lambda ,\mu )}$. Seien ${\displaystyle r,s}$ die Eigenwerte der Adjazenzmatrix ${\displaystyle A}$ von ${\displaystyle \Gamma }$ und ${\displaystyle f,g}$ deren Vielfachheiten.

• Die Parameter von ${\displaystyle \Gamma }$ erfüllen ${\displaystyle (v-k-1)\mu =k(k-\mu -1)}$.^[3]
• Sei ${\displaystyle I\in \mathbb {R} ^{v\times v}}$ die Einheitsmatrix und ${\displaystyle J\in \mathbb {R} ^{v\times v}}$ die Einsmatrix. Dann erfüllt ${\displaystyle A}$ die Gleichung ${\displaystyle AJ=JA=kJ}$, die eine Charakterisierung der regulären Graphen ist. Außerdem erfüllt ${\displaystyle A}$ die Gleichung ${\displaystyle A^{2}=kI+\lambda A+\mu (J-I-A)}$. Erfüllt andersherum die Adjazenzmatrix ${\displaystyle A}$ eines Graphen zu bestimmten ganzen Zahlen ${\displaystyle k,\lambda ,\mu }$ die beiden Gleichungen, so ist der Graph stark regulär mit Parametern ${\displaystyle (v,k,\lambda ,\mu )}$ (oder leer oder vollständig).^[4]
• Es ist ${\displaystyle k}$ ein Eigenwert von ${\displaystyle A}$ zum Eigenvektor ${\displaystyle j=(1,\ldots ,1)^{\mathrm {T} }}$. Er hat genau dann Vielfachheit ${\displaystyle 1}$, wenn ${\displaystyle \Gamma }$ zusammenhängend ist. Die anderen Eigenwerte ${\displaystyle r,s}$ sind die Nullstellen des Polynoms

${\displaystyle x^{2}+(\mu -\lambda )x+(\mu -k)}$.

Setzt man ${\displaystyle r>s}$, so erhält man deren Vielfachheiten über die Gleichungen

${\displaystyle f={\frac {(s+1)k(k-s)}{\mu (s-r)}}}$ und ${\displaystyle g={\frac {(r+1)k(k-r)}{\mu (r-s)}}}$.^[5]

Der Begriff des stark regulären Graphen wurde 1963 von R. C. Bose eingeführt. Die heute üblichen Bezeichnungen für die Parameter ${\displaystyle v,k,\lambda ,\mu }$ eines stark regulären Graphen sowie die Eigenwerte ${\displaystyle r,s}$ und Vielfachheiten ${\displaystyle f,g}$ seiner Adjazenzmatrix wurden wahrscheinlich zuerst 1971 in leicht abgewandelter Form von M. D. Hestenes und D. G. Higman verwendet.^[6]

1. ↑ Ist ${\displaystyle \Gamma }$ leer, so gibt es keine benachbarten Ecken und ${\displaystyle \lambda }$ ist nicht eindeutig bestimmt. Ist ${\displaystyle \Gamma }$ vollständig, so gibt es keine nicht benachbarten Ecken und ${\displaystyle \mu }$ ist nicht eindeutig bestimmt.

• Andries E. Brouwer, H. van Maldeghem: Strongly Regular Graphs (= Encyclopedia of mathematics and its applications. Band 182). Cambridge University Press, Cambridge 2022, ISBN 978-1-00-905722-6 (englisch). 

Commons: Stark reguläre Graphen – Sammlung von Bildern, Videos und Audiodateien

• Eric W. Weisstein: Strongly Regular Graph. In: MathWorld (englisch).

1. ↑ Bart De Bruyn: An Introduction to Incidence Geometry (= Frontiers in Mathematics). Birkhäuser, Cham 2016, ISBN 978-3-319-43811-5, S. 39 (englisch). 
2. ↑ Andries E. Brouwer, H. van Maldeghem: Strongly Regular Graphs (= Encyclopedia of mathematics and its applications. Band 182). Cambridge University Press, Cambridge 2022, ISBN 978-1-00-905722-6, S. 1 (englisch). 
3. ↑ Bart De Bruyn: An Introduction to Incidence Geometry (= Frontiers in Mathematics). Birkhäuser, Cham 2016, ISBN 978-3-319-43811-5, S. 40 (englisch). 
4. ↑ Andries E. Brouwer, H. van Maldeghem: Strongly Regular Graphs (= Encyclopedia of mathematics and its applications. Band 182). Cambridge University Press, Cambridge 2022, ISBN 978-1-00-905722-6, S. 2 (englisch). 
5. ↑ Bart De Bruyn: An Introduction to Incidence Geometry (= Frontiers in Mathematics). Birkhäuser, Cham 2016, ISBN 978-3-319-43811-5, S. 43 (englisch). 
6. ↑ Andries E. Brouwer, H. van Maldeghem: Strongly Regular Graphs (= Encyclopedia of mathematics and its applications. Band 182). Cambridge University Press, Cambridge 2022, ISBN 978-1-00-905722-6, S. 1–2 (englisch).