Anzahl der Ecken einer kleinsten überdeckenden Eckenmenge in einem Graphen.

Im folgenden sei G ein Graph ohne isolierte Ecken. Eine Eckenmenge U von G heißt überdeckende Eckenmenge von G, wenn jede Kante von G mit mindestens einer Ecke aus U inzidiert. Ist U eine überdeckende Eckenmenge von G, und existiert keine überdeckende Eckenmenge U′ von G mit |U′| < |U|, so heißt U minimale überdeckende Eckenmenge und |U| = β(G) Eckenüberdeckungszahl von G.

Eine Eckenmenge I von G heißt unabhängig oder stabil in G, wenn keine zwei Ecken aus I adjazent sind. Ist I eine unabhängige Eckenmenge in G, und gibt es keine unabhängige Eckenmenge I′ in G mit |I′| > |I|, so heißt I maximale unabhängige Eckenmenge in G und |I| = α(G) Unabhängigkeitszahl oder Stabilitätszahl von G.

Eine Kantenmenge L von G heißt überdeckende Kantenmenge von G, wenn jede Ecke aus G mit mindestens einer Kante aus L inzidiert. Ist L eine überdeckende Kantenmenge von G, und existiert keine überdeckende Kantenmenge L′ von G mit |L′| < |L|, so heißt L minimale überdeckende Kantenmenge und |L| = β₀(G) Kantenüberdeckungszahl von G.

Eine Kantenmenge M von G heißt unabhängig, Korrespondenz in G oder Matching von G, wenn keine zwei Kanten aus M inzident sind. Ist M eine unabhängige Kantenmenge in G, und gibt es keine unabhängige Kantenmenge M′ in G mit |M′| > |M|, so heißt M maximale unabhängige Kantenmenge, maximales Matching oder maximale Korrespondenz von G und |M| = α₀(G) Kantenunabhängigkeitszahl oder Matchingzahl. Ein Matching M mit 2|M| = |E(G)| nennt man perfektes Matching oder perfekte Korrespondenz. Offensichtlich ist ein perfektes Matching auch maximal, und besitzt G ein perfektes Matching, so ist G notwendig ein gerader Graph.

Eine Eckenmenge D von G heißt dominierende Eckenmenge oder „dominating set“ von G, wenn jede Ecke aus G, die nicht zu D gehört, zu mindestens einer Ecke aus D adjazent ist. Ist D eine dominierende Eckenmenge von G, und existiert keine dominierende Eckenmenge D′ von G mit |D′| < | D |, so heißt D minimale dominierende Eckenmenge und |D| = γ(G) nennt man Dominanzzahl von G.

Die Ungleichungen α₀(G) ≤ β(G), γ(G) ≤ α(G) und γ(G) ≤ β(G) ergeben sich recht leicht aus den obigen Definitionen. Im Jahre 1959 hat dann T. Gallai die folgenden interessanten Zusammenhänge gefunden:

\begin{eqnarray}\alpha (G)+\beta (G)=\,|E(G)|={\alpha }_{0}(G)+{\beta }_{0}(G).\end{eqnarray}

Daraus ergibt sich wegen α₀(G) ≤ β(G) sofort α(G) ≤ β₀(G). Die Ungleichungen γ(G) ≤ β(G) und γ(G) ≤ α(G) liefern zusammen mit der ersten Gleichung von Gallai die klassische Abschätzung

\begin{eqnarray}\gamma (G)\le |E(G)|/2\end{eqnarray}

In den Jahren 1998/99 haben B.Randerath und L.Volkmann alle Graphen G charakterisiert für die γ(G) = β(G) bzw. γ(G) = α₀(G) gilt. Diese Charakterisierungen liefern unmittelbar polynomiale Algorithmen, mit deren Hilfe man entscheiden kann, ob ein gegebener Graph G die Eigenschaft γ(G) = β(G) bzw. γ(G) = α₀(G) besitzt. Vertiefte Informationen und die neuesten Resultate über diese Graphenparameter findet man in der angegebenen Literatur.

[1] Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, Inc. New York, 1998.
[2] Haynes, T.W.; Hedetniemi, S.T.; Slater, P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker, Inc. New York, 1998.