Knotenüberdeckungszahl

Als Knotenüberdeckungszahl eines Graphen bezeichnet man in der Graphentheorie die Anzahl Knoten, seiner kleinstmöglichen Knotenüberdeckung.

Die Knotenüberdeckungszahl eines Graphen ist mindestens so groß wie seine Paarungszahl, da die Knoten der Kanten einer größten Paarung nur zu einer Paarungskante inzident sein können. Gleichzeitig kann die Knotenüberdeckungszahl höchstens so groß sein, wie das 2-fache der Paarungszahl, da die Knoten aller Paarungskanten eine gültige Knotenüberdeckung ergeben. In bipartiten Graphen stimmen Knotenüberdeckungszahl und Paarungszahl überein.

siehe auch: Cliquen und stabile Mengen