PDF

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

TOTAL DOMINATION OF CARTESIAN PRODUCTS OF GRAPHS

Xinmin Hou

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

Abstract

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.

References

[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