ArticleOriginal scientific text

Title

Total domination of Cartesian products of graphs

Authors 1

Affiliations

  1. Department of Mathematics, University of Science and Technology of China, Hefei, Anhui, 230026, China

Abstract

Let γₜ(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 γₜ(G)γₜ(H) ≤ 5γₜ(G □ H), which improves the known result γₜ(G)γₜ(H) ≤ 6γₜ(G □ H) given by Henning and Rall.

Keywords

total domination number, Cartesian product, Vizing's conjecture

Bibliography

  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.
Pages:
175-178
Main language of publication
English
Received
2006-03-07
Accepted
2006-10-25
Published
2007
Exact and natural sciences