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

Der Paley-Graph der Ordnung 13 ist ein stark regulärer Graph. Er hat die Parameter .

Definition

Bearbeiten

Kombinatorische Definition

Bearbeiten

Sei   ein endlicher Graph mit Eckenmenge   und Kantenmenge  . Dann heißt   stark regulär, falls es drei ganze Zahlen   gibt, sodass

  • jede Ecke genau   Nachbarn hat,
  • je zwei benachbarte Ecken genau   gemeinsame Nachbarn haben und
  • je zwei nicht benachbarte Ecken genau   gemeinsame Nachbarn haben.

Ist   die Anzahl der Ecken von  , so nennt man   einen stark regulären Graphen mit Parametern  .

Oft wird für einen stark regulären Graphen zusätzlich verlangt, dass   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.

Definition über die Adjazenzmatrix

Bearbeiten

Wie die regulären Graphen lassen sich auch die stark regulären Graphen über ihre Adjazenzmatrix charakterisieren: Sei   ein endlicher Graph mit   und Adjazenzmatrix  . Sei   der Einsvektor. Dann heißt    -regulär, wenn   ein Eigenvektor von   zum Eigenwert   ist. Ist   ein regulärer Graph, so heißt er stark regulär, wenn   genau zwei Eigenwerte hat, die zu   orthogonale Eigenvektoren besitzen. Diese zwei Eigenwerte werden üblicherweise mit   und deren Vielfachheiten mit   bezeichnet.[2]

Beispiele

Bearbeiten
  • Die Kreisgraphen   und   mit vier und fünf Ecken sind stark regulär mit Parametern   und  . Bei den Kreisgraphen   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  .
  • Die disjunkte Vereinigung   von   vollständigen Graphen   mit   ist stark regulär. Sie hat Parameter  .
  • Der vollständig multipartite Graph  , dessen   Partitionsklassen alle genau   Ecken haben, ist stark regulär. Er hat Parameter  .
  • Der Komplementgraph eines stark regulären Graphen mit Parametern   ist stark regulär. Er hat Parameter  .
  • Der Line-Graph des vollständigen Graphen   mit   Ecken ist stark regulär. Er hat Parameter  .

Eigenschaften

Bearbeiten

In diesem Abschnitt sei   ein stark regulärer Graph mit Parametern  . Seien   die Eigenwerte der Adjazenzmatrix   von   und   deren Vielfachheiten.

  • Die Parameter von   erfüllen  .[3]
  • Sei   die Einheitsmatrix und   die Einsmatrix. Dann erfüllt   die Gleichung  , die eine Charakterisierung der regulären Graphen ist. Außerdem erfüllt   die Gleichung  . Erfüllt andersherum die Adjazenzmatrix   eines Graphen zu bestimmten ganzen Zahlen   die beiden Gleichungen, so ist der Graph stark regulär mit Parametern   (oder leer oder vollständig).[4]
  • Es ist   ein Eigenwert von   zum Eigenvektor  . Er hat genau dann Vielfachheit  , wenn   zusammenhängend ist. Die anderen Eigenwerte   sind die Nullstellen des Polynoms
 .
Setzt man  , so erhält man deren Vielfachheiten über die Gleichungen
  und  .[5]

Geschichte

Bearbeiten

Der Begriff des stark regulären Graphen wurde 1963 von R. C. Bose eingeführt. Die heute üblichen Bezeichnungen für die Parameter   eines stark regulären Graphen sowie die Eigenwerte   und Vielfachheiten   seiner Adjazenzmatrix wurden wahrscheinlich zuerst 1971 in leicht abgewandelter Form von M. D. Hestenes und D. G. Higman verwendet.[6]

Anmerkungen

Bearbeiten
  1. Ist   leer, so gibt es keine benachbarten Ecken und   ist nicht eindeutig bestimmt. Ist   vollständig, so gibt es keine nicht benachbarten Ecken und   ist nicht eindeutig bestimmt.

Literatur

Bearbeiten
  • 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).
Bearbeiten
Commons: Stark reguläre Graphen – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

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