×

Strong transversals in hypergraphs and double total domination in graphs. (English) Zbl 1221.05254

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.

MSC:

05C65 Hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link