×
![]( "Buchcover ISBN 9783843947701")
On Simultaneous Domination and Mixed Connectivity in Graphs
von Sebastian S. JohannDie Graphentheorie ist ein florierendes Themengebiet der modernen Mathematik und bietet großartige Lösungsansätze für kombinatorische Probleme. Eine wichtige Rolle spielt das dominierende Mengen-Problem, bei dem man eine Menge an Knoten eines Graphen sucht, so dass jeder Knoten des Graphen in dieser Menge oder benachbart zu einem Knoten in dieser Menge ist. Dieses Problem hat ein breites Anwendungsspektrum in verschiedenen Bereichen wie z. B. der Informatik, der Physik, der Nachrichtentechnik, der Sozialwissenschaft usw.
In dieser Arbeit betrachten wir eine natürliche Erweiterung des dominierenden Mengen-Problems, bei der man mehrere Graphen gleichzeitig dominiert. Genauer gesagt, für eine gegebene Menge an Graphen ist eine simultan dominierende Menge eine Menge von Knoten, die in jedem dieser Graphen eine dominierende Menge induziert. Unter anderem untersuchen wir das Problem der gleichzeitigen Domination aller spannenden Bäume eines Graphen, aller Kreises fester Länge in einem Graphen sowie jedes kürzesten Weges zwischen zwei Knoten in einem Graphen. Wir konzentrieren uns auf die Komplexität und die algorithmischen Aspekte dieser Probleme. Obwohl sich die meisten Probleme als NP-vollständig herausstellen, stellen wir exakte Algorithmen auf. Außerdem leiten wir fpt-Algorithmen und Approximationsalgorithmen her.
Im zweiten Teil der Arbeit diskutieren wir eine Mischform des Zusammenhangs eines Graphen, bei der man sowohl Knoten als auch Kanten gleichzeitig löschen kann. Eine Vermutung von Beineke und Harary besagt, dass, wenn man zwei Knoten s und t eines Graphen mit k Knoten und l Kanten trennen kann, dies aber mit k-1 Knoten und l Kanten als auch mit k Knoten und l-1 Kanten nicht möglich ist, dann gibt es k+l Kanten-disjunkte s-t Wege, von denen k+1 intern Knoten-disjunkt sind. Wir zeigen, dass diese Vermutung für l=2 erfüllt ist. Anschließend benutzen wir dieses Ergebnis, um die allgemeine Vermutung für Graphen mit einer Baumweite von höchstens 3 zu beweisen.
In dieser Arbeit betrachten wir eine natürliche Erweiterung des dominierenden Mengen-Problems, bei der man mehrere Graphen gleichzeitig dominiert. Genauer gesagt, für eine gegebene Menge an Graphen ist eine simultan dominierende Menge eine Menge von Knoten, die in jedem dieser Graphen eine dominierende Menge induziert. Unter anderem untersuchen wir das Problem der gleichzeitigen Domination aller spannenden Bäume eines Graphen, aller Kreises fester Länge in einem Graphen sowie jedes kürzesten Weges zwischen zwei Knoten in einem Graphen. Wir konzentrieren uns auf die Komplexität und die algorithmischen Aspekte dieser Probleme. Obwohl sich die meisten Probleme als NP-vollständig herausstellen, stellen wir exakte Algorithmen auf. Außerdem leiten wir fpt-Algorithmen und Approximationsalgorithmen her.
Im zweiten Teil der Arbeit diskutieren wir eine Mischform des Zusammenhangs eines Graphen, bei der man sowohl Knoten als auch Kanten gleichzeitig löschen kann. Eine Vermutung von Beineke und Harary besagt, dass, wenn man zwei Knoten s und t eines Graphen mit k Knoten und l Kanten trennen kann, dies aber mit k-1 Knoten und l Kanten als auch mit k Knoten und l-1 Kanten nicht möglich ist, dann gibt es k+l Kanten-disjunkte s-t Wege, von denen k+1 intern Knoten-disjunkt sind. Wir zeigen, dass diese Vermutung für l=2 erfüllt ist. Anschließend benutzen wir dieses Ergebnis, um die allgemeine Vermutung für Graphen mit einer Baumweite von höchstens 3 zu beweisen.