Stark regulärer Graph
# 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 $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.

