Stark regulärer Graph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Der Paley-Graph der Ordnung 13 ist ein stark regulärer Graph. Er hat die Parameter .

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.

Kombinatorische Definition

[Bearbeiten | Quelltext 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 | Quelltext 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]

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

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]

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]

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

Einzelnachweise

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