×

Connected graphs with maximum total domination number. (English) Zbl 0958.05100

For any ordinary graph \(G=(V,E)\), the total domination number \(\gamma_t(G)\) is the minimum cardinality of subsets \(S\) of \(V\) such that every vertex of \(V\) has a neighbour in \(S\). It is known [E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs, Networks 10, 211-219 (1980; Zbl 0447.05039)] that \(\gamma_t\geq\lfloor\frac{2n}3\rfloor\), for \(|V|>2\). This paper characterizes graphs that attain that bound.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C75 Structural characterization of families of graphs
05C35 Extremal problems in graph theory

Citations:

Zbl 0447.05039
PDF BibTeX XML Cite