Die Struktur dominierender Mengen in Graphen

Abstract

Ein zentrales Konzept in der Graphentheorie ist das der Dominierung. Eine dominierende Menge eines Graphen G ist eine Teilmenge X der Knoten, für die jeder Knoten aus V (G) \ X einen Nachbarn in X besitzt. Anschaulich formuliert, eine dominierende Menge in einem Netzwerk ist ein Komitee, bei dem gilt, dass jedes Nicht-Mitglied ein Mitglied kennt. Dominierende Mengen, ihre Anwendungen und Varianten sind in der Forschungsliteratur sehr gut untersucht. In dieser Arbeit tragen wir grundlegende Untersuchungen zu den strukturellen und algorithmischen Eigenschaften dominierender Mengen bei. Im Mittelpunkt stehen dabei spezielle dominierende Mengen, deren induzierte Teilgraphen zusätzlichen strukturellen Bedingungen genügen.