A new upper bound on the total domination number of a graph (Q1010625)

Summary: A set \(S\) of vertices in a graph \(G\) is a total dominating set of \(G\) if every vertex of \(G\) is adjacent to some vertex in \(S\). The minimum cardinality of a total dominating set of \(G\) is the total domination number of \(G\). Let \(G\) be a connected graph of order\(n\) with minimum degree at least two and with maximum degree at least three. We define a vertex as large if it has degree more than2 and we let \({\mathcal L}\) be the set of all large vertices of \(G\). Let \(P\) be any component of \(G - {\mathcal L}\); it is a path. If \(|P| \equiv 0 \pmod 4\) and either the two ends of \(P\) are adjacent in \(G\) to the same large vertex or the two ends of \(P\) are adjacent to different, but adjacent, large vertices in \(G\), we call \(P\) a 0-path. If \(|P| \geq 5\) and \(|P| \equiv 1 \pmod 4\) with the two ends of \(P\) adjacent in \(G\) to the same large vertex, we call \(P\) a 1-path. If \(|P| \equiv 3 \pmod 4\), we call \(P\) a 3-path. For \(i \in \{0,1,3\}\), we denote the number of \(i\)-paths in \(G\) by \(p_i\). We show that the total domination number of \(G\) is at most\((n + p_0 + p_1 + p_3)/2\). This result generalizes a result shown in several manuscripts (see, for example, \textit{D. Archdeacon}, \textit{J. Ellis-Monaghan}, \textit{D. Fisher}, \textit{D. Froncek}, \textit{P.C.B. Lam}, \textit{S. Seager}, \textit{B. Wei}, and \textit{R. Yuster}, J.Graph Theory 46, No.\,3, 207--210 (2004; Zbl 1041.05057)) which states that if \(G\) is a graph of order \(n\) with minimum degree at least three, then the total domination of \(G\) is at most \(n/2\). It also generalizes a result by \textit{P.C.B. Lam} and \textit{B. Wei} [Util. Math. 72, 223--240 (2007; Zbl 1120.05065)] stating that if \(G\) is a graph of order \(n\) with minimum degree at least two and with no degree-2 vertex adjacent to two other degree-2 vertices, then the total domination of \(G\) is at most \(n/2\).