$k$-Tuple total domination and mycieleskian graphs

Document Type : Research Paper

Author

UMA (University of Mohaghegh Ardabili)

Abstract

‎Let $k$ be a positive integer‎. ‎A subset $S$ of $V(G)$ in a graph $G$‎ ‎is a $k$-tuple total dominating set of $G$ if every vertex of $G$‎ ‎has at least $k$ neighbors in $S$‎. ‎The $k$-tuple total domination‎ ‎number $\gamma _{\times k,t}(G)$ of $G$ is the minimum cardinality‎ ‎of a $k$-tuple total dominating set of $G$‎. ‎In this paper for a‎ ‎given graph $G$ with minimum degree at least $k$‎, ‎we find some sharp‎ ‎lower and upper bounds on the $k$-tuple total domination number of the $m$‎ -‎Mycieleskian graph $\mu _{m}(G)$ of $G$ in terms on $k$ and $\gamma‎ ‎_{\times k,t}(G)$‎. ‎Specially we give the sharp bounds $\gamma‎ ‎_{\times k,t}(G)+1$ and $\gamma _{\times k,t}(G)+k$ for $\gamma‎ ‎_{\times k,t}(\mu _1(G))$‎, ‎and characterize graphs with $\gamma‎ ‎_{\times k,t}(\mu _1(G))=\gamma _{\times k,t}(G)+1$‎.

Keywords

Main Subjects


F. Harary, T. W. Haynes (2000). Double domination in graphs. Ars Combin.. 55, 201-213 T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of Domination in Graphs. Marcel Dekker, New York. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (1998). Domination in Graphs: Advanced Topics. Marcel Dekker, New York. M. A. Henning, A. P. Kazemi (2010). k-tuple total domination in graphs. Discrete Applied Mathematics. 158, 1006-1011 M. A. Henning, A. P. Kazemi k-tuple total domination in cross product graphs. Journal of Combinatorial Optimization. A. P. Kazemi k-tuple total domination in complementary prisms. ISRN Discrete Mathematics. C. Tardif (2001). Fractional chromatic numbers of cones over graphs. J. Graph Theory. 38, 87-94 D. B. West (2001). Introduction to Graph Theory, (2nd edition). Prentice Hall, USA.
  • Receive Date: 01 November 2011
  • Revise Date: 27 November 2011
  • Accept Date: 25 November 2011
  • Published Online: 01 March 2012