A new upper bound on the total domination number of a graph
type: Item
instance of: scholarly article
title: A new upper bound on the total domination number of a graph
zbMATH Open document ID: 1158.05046
author: Michael A. Henning
author: A. Yeo
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129703
full work available at URL: v14i1r65.html
review text: 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\).
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5540843
zbMATH Keywords: minimal total dominating set
zbMATH Keywords: total domination number
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540843