Discussiones Mathematicae Graph Theory 27(1) (2007) 175-178
doi: 10.7151/dmgt.1353

[BIBTex] [PDF] [PS]


Xinmin Hou

Department of Mathematics
University of Science and Technology of China
Hefei, Anhui, 230026, China
e-mail: xmhou@ustc.edu.cn


Let γt(G) and γpr(G) denote the total domination and the paired domination numbers of graph G, respectively, and let G□H denote the Cartesian product of graphs G and H. In this paper, we show that γt(G)γt(H) ≤ 5γt(G□H), which improves the known result γt(G)γt(H) ≤ 6γt(G□H) given by Henning and Rall.

Keywords: total domination number, Cartesian product, Vizing's conjecture.

2000 Mathematics Subject Classification: 05C69.


[1] E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304.
[2] W.E. Clark and S. Suen, An inequality related to Vizing's conjecture, Electron. J. Combin. 7 (2000), No.1, Note 4, 3pp. (electronic).
[3] M.A. Henning and D.F. Rall, On the total domination number of Cartesian products of graphs, Graphs and Combinatorics 21 (2005) 63-69, doi: 10.1007/s00373-004-0586-8.
[4] T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206, doi: 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F.
[5] V.G. Vizing, Some unsolved problems in graph theory, Usp. Mat. Nauk 23 (1968), no. 6(144) 117-134.

Received 7 March 2006
Revised 25 October 2006