Henning, Michael A.; Yeo, Anders Strong transversals in hypergraphs and double total domination in graphs. (English) Zbl 1221.05254 SIAM J. Discrete Math. 24, No. 4, 1336-1355 (2010). Summary: 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. Cited in 21 Documents MSC: 05C65 Hypergraphs 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:total domination; transversals; cubic graphs; hypergraphs PDFBibTeX XMLCite \textit{M. A. Henning} and \textit{A. Yeo}, SIAM J. Discrete Math. 24, No. 4, 1336--1355 (2010; Zbl 1221.05254) Full Text: DOI Link