scientific article; zbMATH DE number 2076802

From MaRDI portal
Publication:4470232





A subset \(D\) of the vertex set of a graph \(G\) is called total dominating in \(G\), if each vertex of \(G\) (including the vertices of \(D\) themselves) is adjacent to a vertex of \(D\). The minimum number of vertices of a total dominating set in \(G\) is the total domination number \(\gamma_t(G)\) of \(G\). \textit{O. Favaron}, \textit{M. A. Henning}, \textit{C. M. Mynhart} and \textit{J. Puech} [J. Graph Theory 34, 9--19 (2000; Zbl 0945.05047)] conjectured that \(\gamma_t(G)\leq n /2\), where \(n\) is the number of vertices of \(G\). Now let \(\delta\) be the minimum degree of a vertex in \(G\) and let \(\delta> 1\). In this paper it is proved that \(\gamma_t(G)\leq {1+\ln(2\delta)\over\delta} n\). This proves the above-mentioned conjecture at \(\delta\geq 8\). The paper ends by a ``note added in proof. In it the author informs that the original conjecture \(\gamma_t(G)\leq n/2\) was proved by Peter Che Bor Lam and Bing Wei.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4470232)