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

作者：Henning Michael A^*; Yeo Anders

来源：Electronic Journal of Combinatorics, 2007, 14(1): R65.

• bounds
• path components
• total domination number

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 atleast two and with maximum degree atleast three. We define a vertex as large if it has degree more than 2 and we let L be the set of all large vertices of G. Let P be any component of G-L; it is a path. If vertical bar P vertical bar 0 (mod 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 vertical bar P vertical bar >= 5 and vertical bar P vertical bar 1 (mod 4) with the two ends of P adjacent in G to the same large vertex, we call P a 1-path. If vertical bar P vertical bar 3 (mod 4), we call P a 3-path. For i epsilon {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, forexample, J. Graph Theory 46 (2004), 207-210) 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 Lam and Wei 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.

• 出版日期2007-9-7