Bezeichnung für einen Eigenwert der Adjazenzmatrix eines Graphen (Eigenwert).

Es sei G ein Graph und A_G = ((a_ij)) seine Adjazenzmatrix. Ist der Graph G von der Ordnung n, so ist A_G = ((a_ij)) eine symmetrische (n × n)-Matrix, deren Hauptdiagonalenelemente a_ii sämtlich Null sind. Das charakteristische Polynom P_G(x) = det(A_G − xI) der Matrix A_G, wobei I die (n × n)-Einheitsmatrix bedeutet, wird auch charakteristisches Polynom von G genannt, und seine Nullstellen heißen Eigenwerte von G.

Als reelle symmetrische Matrix besitzt A_G nur reelle Eigenwerte, die in der Form \begin{eqnarray}{\lambda }_{1}\ge {\lambda }_{2}\ge \cdots \ge {\lambda }_{n}\end{eqnarray} angeordnet seien. Diese Folge der Eigenwerte wird auch das Spektrum von G genannt.

Natürlich ist das Spektrum eines Graphen unabhängig von der Numerierung seiner Ecken, und isomorphe Graphen haben die gleichen Eigenwerte. Beispielsweise besitzt der vollständige Graph K_n das Spektrum λ₁ = n − 1 und λ₂ = λ₃ = … = λ_n = −1, und der vollständige bipartite Graph K_r,s das Spektrum \({\lambda }_{1}=\sqrt{rs}\), λ₂ = λ₃ = … = λ_r+s−1 = 0 und \({\lambda }_{r+s}=-\sqrt{rs}\).

Wäre die Struktur eines Graphen eindeutig durch sein Spektrum bestimmt, so könnte man das bekannte Graphenisomorphieproblem dadurch lösen, daß man die Eigenwerte der entsprechenden Graphen berechnet. Daß diese Methode im allgemeinen jedoch nicht zum Ziel führt, zeigen schon die nicht isomorphen Graphen K_1,4 und K₁ ∪ C₄, die beide das Spektrum 2, 0, 0, 0, −2 besitzen, wobei C₄ der Kreis der Länge 4 ist.

Darüberhinaus gibt es auch nicht isomorphe zusammenhängende Graphen mit gleichem Spektrum, und mit Hilfe einer Konstruktion von A.J. Hoffman (1972) erhält man sogar das folgende Ergebnis.

Zu jeder natürlichen Zahl m existiert eine Zahl N, so daß für alle ganzen Zahlen n ≥ N mindestens m nicht isomorphe reguläre und zusammenhängende Graphen der Ordnung n mit dem gleichen Spektrum existieren.

Sind G₁, G₂, …, G_η die Zusammenhangskomponenten eines Graphen G, so liefert der Determinantenmultiplikationsatz die Identität \begin{eqnarray}{P}_{G}(x)={P}_{{G}_{1}}(x){P}_{{G}_{2}}(x)\ldots {P}_{{G}_{\eta }}(x).\end{eqnarray}

Folglich erhält man das Spektrum eines Graphen aus den Spektren seiner Zusammenhangskomponenten. Aus der Tatsache, daß die Summe der Eigenwerte (mit Vielfachheit) einer (n × n)-Matrix ((a_ij)) mit deren Spur, also mit a₁₁ + a₂₂ + … + a_nn, übereinstimmt, ergibt sich für das Spektrum von G unmittelbar die Aussage \begin{eqnarray}{\lambda }_{1}+{\lambda }_{2}+\cdots +{\lambda }_{n}=0.\end{eqnarray}

Ist G ein zusammenhängender Graph der Ordnung n vom Maximalgrad Δ(G), so beweist man die meisten der folgenden Eigenschaften mit Hilfe von klassischen Resultaten, die O. Perron 1907 und G. Frobenius 1912 zur allgemeinen Matrizentheorie entwickelt haben.

Im Jahre 1967 hat H.S. Wilf einen interessanten Zusammenhang zwischen den Eigenwerten eines Graphen G und seiner chromatischen Zahl χ(G) herausgefunden.

Es sei G ein zusammenhängender Graph und λ₁sein größter Eigenwert. Dann gilt \begin{eqnarray}\chi (G)\le 1+{\lambda }_{1},\end{eqnarray}und die obere Schranke wird in dieser Abschätzung genau dann erreicht, wenn G der vollständige Graph oder ein Kreis ungerader Länge ist.

Wegen (i) verallgemeinert dieser Satz von Wilf den bekannten Satz von Brooks χ(G) ≤ 1 + Δ(G), wobei genau dann die Gleichheit gilt, wenn G der vollständige Graph oder ein Kreis ungerader Länge ist.

Vertiefte Informationen zur Theorie der Eigenwerte von Graphen findet man beispielweise in der Monographie [1].

[1] Cvetkovic, D.M.; Doob, M.; Sachs, H.: Spectra of Graphs. Johann Ambrosius Barth, Heidelberg Leipzig, 3rd edition, 1995.