Strong Transversals in Hypergraphs and Double Total Domination in Graphs
Michael A. Henning, Anders Yeo · SIAM Journal on Discrete Mathematics · 2010
Let H be a 3-uniform hypergraph of order n and size m, and let T be a subset of vertices of H. The set T is a strong transversal in H if T contains at least two vertices from every edge of H. The strong transversal number $\tau_s(H)$ of H is the minimum size of a strong transversal in H. We show that $7\tau_s(H)\leq4n+2m$, and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph H of order $n\geq6$ and size m that achieves equality in this bound. A set S of vertices in a graph G is a double total dominating set of G if every vertex of G is adjacent to at least two vertices in S. The minimum cardinality of a double total dominating set of G is the double total domination number $\gamma_{\times2,t}(G)$ of G. Let G be a connected graph of order n with minimum degree at least three. As an application of our hypergraph results, we show that $\gamma_{\times2,t}(G)\leq6n/7$ with equality if and only if G is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if G is not the Heawood graph, we show that $\gamma_{\times2,t}(G)\leq11n/13$, while if G is a cubic graph different from the Heawood graph, we show that $\gamma_{\times2,t}(G)\leq5n/6$, and this bound is sharp.