Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A new upper bound on the total domination number of a graph. | A new upper bound on the total domination number of a graph 1 Michael A. Henning and 2Anders Yeo 1School of Mathematical Sciences University of KwaZulu-Natal Pietermaritzburg 3209 South Africa 2Department of Computer Science Royal Holloway University of London Egham Surrey TW20 OEX UK Submitted Sep 7 2006 Accepted Sep 3 2007 Published Sep 7 2007 Abstract 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 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 PI 0 mod4 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 PI 5 and PI 1 mod4 with the two ends of P adjacent in G to the same large vertex we call P a 1-path. If PI 3 mod 4 we call P a 3-path. For i 2 0 1 3g we denote the number of i-paths in G by Pi. We show that the total domination number of G is at most n p0 p1 Ps 2. This result generalizes a result shown in several manuscripts see for example 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. Keywords bounds path components total domination number AMS subject classification 05C69 Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. THE ELECTRONIC JOURNAL OF COMBINATORICS 14
