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

Brigham, Robert C.; Carrington, Julie R.; Vitray, Richard P.

J. Comb. Math. Comb. Comput. 34, 81-95 (2000).

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.

Reviewer: William G.Brown (Montréal)

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