Total Domination in Graphs with Large Minimum Degree
Final Report Abstract
Ein Hypergraph H = (V; E) ist eine endliche Menge V von Elementen, genannt Knoten, zusammen mit einer endlichen Menge E von Teilmengen von V , genannt Kanten. Ein Hypergraph H ist k-uniform, falls jede Kante von H die Kardinalität k hat. Ein 2-uniformer Hypergraph wird Graph genannt. Eine Dominanzmenge D in einem Hypergraphen H = (V; E) ist eine Teilmenge von V, so dass jeder Knoten, der nicht zu D gehört, zu mindestens einer Kante gehört, zu der auch mindestens ein Knoten aus D gehört. Die Dominanzzahl von H ist die kleinste Ordnung einer Dominanzmenge in H. Eine Teilmenge T der Knoten eines Hypergraphen H ist eine Transversale, falls für jede Kante e ∊ E der Schnitt mit T nicht leer ist. Die Transversalenzahl von H ist die kleinste Ordnung einer Transversale in H. Während des Projektes charakterisierten wir für k = 3 und k = 5 k-uniforme Hypergraphen mit großer Dominanzzahl. Überraschend war dabei, dass eine Charakterisierung für k = 4 als zu umfangreich herausstellte, da es zu viele völlig unterschiedliche k-uniforme Hypergraphen mit großer Dominanzzahl gibt. Darüberhinaus charakterisierten wir für k = 2 und k = 4 k-uniforme Hypergraphen mit großer Transversalenzahl. Überraschend war dabei, dass es für jedes solche k nur zwei solcher Hypergraphen gibt, wohingegen es für k = 3 mehrere unendlich große Familien solcher Hypergraphen gibt. Ein 2-uniformer Hypergraph wird Graph genannt. Eine totale Dominanzmenge eines Graphen G = (V; E) ist eine Teilmenge der Knoten T ⊆ V , so dass jeder Knoten v ∊ V zu einem Knoten aus T benachbart ist. Eine lokalisierende totale Dominanzmenge L ist eine totale Dominanzmenge mit der zus atzlichen Eigenschaft, dass unterschiedliche Knoten in V \ L zu unterschiedlichen Teilmenge von L benachbart sind. Die lokalisierende totale Dominanzzahl von G ist die kleinste Ordnung einer lokalisierenden totalen Dominanzmenge in G. Im zweiten Teil des Projektes bewiesen wir eine obere Schranke zur lokalisierenden totalen Dominanzzahl und charakterisierten die Graphen, die diese obere Schranke annehmen.
Publications
- Hypergraphs with Large Domination Number and with Edge Sizes at Least Three, Discrete Appl. Math. 160 (2012), 1757-1765
M. A. Henning und C. Löwenstein
- Hypergraphs with Large Transversal Number and with Edge Sizes at Least Four, Cent. Eur. J. Math. 10 (2012), 1133-1140
M. A. Henning und C. Löwenstein
- Locating-total domination in claw-free cubic graphs, Discrete Math. 312 (2012), 3107-3116
M. A. Henning und C. Löwenstein
