Stark regulärer Graph

Der Paley-Graph der Ordnung 13 ist ein stark regulärer Graph. Er hat die Parameter $(13,6,2,3)$.

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

Definition

Kombinatorische Definition

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

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

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

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

Definition über die Adjazenzmatrix

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

Beispiele

• Die Kreisgraphen $C_{4}$ und $C_{5}$ mit vier und fünf Ecken sind stark regulär mit Parametern $(4,2,0,2)$ und $(5,2,0,1)$. Bei den Kreisgraphen $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 $(10,3,0,1)$.
• Die disjunkte Vereinigung $aK_{m}$ von $a\geq 2$ vollständigen Graphen $K_{m}$ mit $m\geq 2$ ist stark regulär. Sie hat Parameter $(am,m-1,m-2,0)$.
• Der vollständig multipartite Graph $K_{a\times m}$, dessen $a\geq 2$ Partitionsklassen alle genau $m\geq 2$ Ecken haben, ist stark regulär. Er hat Parameter $(am,(a-1)m,(a-2)m,(a-1)m)$.
• Der Komplementgraph eines stark regulären Graphen mit Parametern $(v,k,\lambda ,\mu )$ ist stark regulär. Er hat Parameter $(v,v-k-1,v-2k+\mu -2,v-2k+\lambda )$.
• Der Line-Graph des vollständigen Graphen $K_{m}$ mit $m\geq 4$ Ecken ist stark regulär. Er hat Parameter $({\tbinom {m}{2}},2(m-2),m-2,4)$.

Eigenschaften

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

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

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

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

$f={\frac {(s+1)k(k-s)}{\mu (s-r)}}$ und $g={\frac {(r+1)k(k-r)}{\mu (r-s)}}$.

Geschichte

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

Literatur

• 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). 

Weblinks

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

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