No label defined (Q4470232)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2076802
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2076802 |
Statements
22 June 2004
0 references
total domination number
0 references
minimum degree
0 references
total dominating set
0 references
0.93765473
0 references
0.9269351
0 references
0.92472917
0 references
0.9234369
0 references
0.91611516
0 references
0 references
0.91234255
0 references
0.9103366
0 references
0.9076283
0 references
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.
0 references