Discussiones Mathematicae Graph Theory 32(4) (2012) 629-641
doi: 10.7151/dmgt.1632

[BIBTex] [PDF] [PS]

On the Total Restrained Domination Number of Direct Products of Graphs

Wai Chee Shiu

Department of Mathematics, Hong Kong Baptist University
224 Waterloo Road, Kowloon Tong, Hong Kong, China

Hong-Yu Chen

School of Mathematics and System Sciences, Shandong University
Jinan, Shandong Province, 250100, China

Xue-Gang Chen

Department of Mathematics, North China Electric Power University
Beijing, 102206, China

Pak Kiu Sun

Department of Mathematics, Hong Kong Baptist University
224 Waterloo Road, Kowloon Tong, Hong Kong, China


Let G = (V,E) be a graph. A total restrained dominating set is a set S ⊆ V where every vertex in V∖S is adjacent to a vertex in S as well as to another vertex in V∖S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by γrt(G), is the smallest cardinality of a total restrained dominating set of G. We determine lower and upper bounds on the total restrained domination number of the direct product of two graphs. Also, we show that these bounds are sharp by presenting some infinite families of graphs that attain these bounds.

Keywords: total domination number, total restrained domination number, direct product of graphs

2010 Mathematics Subject Classification: 05C69.


[1]R. Chérifi, S. Gravier, X. Lagraula, C. Payan and I. Zigham, Domination number of cross products of paths, Discrete Appl. Math. 94 (1999) 101--139, doi: 10.1016/S0166-218X(99)00016-5.
[2]X.G. Chen, W.C. Shiu and H.Y. Chen, Trees with equal total domination and total restrained domination numbers, Discuss. Math. Graph. Theory 28 (2008) 59--66, doi: 10.7151/dmgt.1391.
[3]M. El-Zahar, S. Gravier and A. Klobucar, On the total domination number of cross products of graphs, Discrete Math. 308 (2008) 2025--2029, doi: 10.1016/j.disc.2007.04.034.
[4]T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, New York, 1998).
[5]D.X. Ma, X.G. Chen and L. Sun, On total restrained domination in graphs, Czechoslovak Math. J. 55 (2005) 165--173, doi: 10.1007/s10587-005-0012-2.
[6]D.F. Rall, Total domination in categorical products of graphs, Discuss. Math. Graph Theory 25 (2005) 35--44, doi: 10.7151/dmgt.1257.
[7]M. Zwierzchowski, Total domination number of the conjunction of graphs, Discrete Math. 307 (2007) 1016--1020, doi: 10.1016/j.disc.2005.11.047.

Received 26 April 2011
Revised 28 November 2011
Accepted 30 November 2011