Benutzer:SeGiba/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 regulären Graphens, dass alle seine Ecken gleich viele Nachbarn haben, erfüllt ein stark regulärer Graph noch Folgendes: Je zwei benachbarte Ecken haben gleich viele gemeinsame Nachbarn und je zwei nicht benachbarte Ecken haben gleich viele gemeinsame Nachbarn.

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 $n=|V|$ die Anzahl der Ecken von $\Gamma$, so nennt man $\Gamma$ einen stark regulären Graphen mit Parametern $(n,k,\lambda ,\mu )$.

Charakterisierung ü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 $n=|V|$ und Adjazenzmatrix $A\in \mathbb {R} ^{n\times n}$. Sei $j=(1,\ldots ,1)^{\mathrm {T} }\in \mathbb {R} ^{n}$ der Einsvektor. Der Graph $\Gamma$ ist genau dann regulär, wenn $j$ ein Eigenvektor von $A$ ist. Er ist genau dann stark regulär, wenn $A$ zusätzlich noch 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.

Eigenschaften

Sei $\Gamma =(V,E)$ ein stark regulärer Graph mit Parametern $(n,k,\lambda ,\mu )$ und Adjanzenzmatrix $A\in \mathbb {R} ^{n\times n}$.

• Sei $I\in \mathbb {R} ^{n\times n}$ die Einheitsmatrix und $J\in \mathbb {R} ^{n\times n}$ die Einsmatrix. Dann erfüllt $A$ die Gleichung $AJ=JA=kJ$, die von den Adjazenzmatrizen aller regulären Graphen erfüllt wird. Außerdem erfüllt $A$ die Gleichung $A^{2}=kI+\lambda A+\mu (J-I-A)$. Erfüllt andersherum eine Adjazenzmatrix zu bestimmten Konstanten $k,\lambda ,\mu$ die beiden Gleichungen, so ist der zur Matrix gehörende Graph ein stark regulärer Graph (oder ein vollständiger Graph oder ein Graph ohne Kanten).

Geschichte

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

Einzelnachweise

Kategorie:Regulärer Graph