Home > News > Mike Henning: Total Domination in Graphs and Transversals in Hypergraphs

Mike Henning: Total Domination in Graphs and Transversals in Hypergraphs

Date: 28. 5. 2017
Source: Discrete mathematics seminar
Torek, 30. 5. 2017, od 10h do 12h, Plemljev seminar, Jadranska 19
Povzetek. The total domination number of a graph G is the minimum cardinality of a set S of vertices so that every vertex of G is adjacent to a vertex in S, while the transversal number of a hypergraph H is the minimum cardinality of a subset of vertices in H that has a nonempty intersection with every edge of H. Much of the recent interest in total domination in graphs arises from the fact that total domination in graphs can be translated to the problem of finding transversals in hypergraphs since the transversal number of the open neighborhood hypergraph of a graph is precisely the total domination number of the graph. We explore this transition from total domination in graphs to transversals in hypergraphs and discuss several recent results on total domination in graphs obtained using transversals in hypergraphs that appear difficult to obtain using purely graph theoretic techniques. For example, we prove the conjecture that if G is a quadrilateral-free graph with minimum degree at least 4, then the total domination number is at most two-fifths the order. In order to prove this result, we first prove some key results on transversals in linear hypergraphs, as well as results on matchings in graphs.