Total perfect codes‎, ‎OO-irredundant and total subdivision in graphs

Document Type : Research Paper


Department of Mathematics‎, ‎Alzahra University‎, ‎P.O. Box 19834, Tehran‎, ‎Iran.


‎Let $G=(V(G),E(G))$ be a graph‎, ‎$\gamma_t(G)$. Let $ooir(G)$ be the total domination and OO-irredundance number of $G$‎, ‎respectively‎. ‎A total dominating set $S$ of $G$ is called a $\textit{total perfect code}$ if every vertex in $V(G)$ is adjacent to exactly one vertex of $S$‎. ‎In this paper‎, ‎we show that if $G$ has a total perfect code‎, ‎then $\gamma_t(G)=ooir(G)$‎. ‎As a consequence, we determine the value of $ooir(G)$ for some classes of graphs‎.


Main Subjects

E. J. Cockayne, S. Finbow and J. S. Swarts, OO-irredundance and maximum degree in paths and trees, J. Combin. Math. Combin. Comput. 73 (2010) 223--236.
O. Favaron, H. Karami and S. M. Sheikholeslami, Bounding the total domination subdivision number of a graph in terms of its order, J. Comb. Optim. 21 (2011), no. 2, 209--218.
H. Gavlas and K. Schultz, Efficient open domination. The Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications, 11 pages, Electron. Notes Discrete Math., 11, Elsevier Sci. B. V., Amsterdam, 2002.
T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, J. Knisely and L. C. van der Merwe, Domination subdivision numbers, Discuss. Math. Graph Theory 21 (2001), no. 2, 239--253.
T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc., New York, 1998.
T. W. Haynes, S. T. Hedetniemi and L. C. van der Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003) 115--128.
M. A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009), no. 1, 32--63.
M. A. Henning and A. Yeo, Total Domination in Graphs, Monographs in Mathematics, Springer, New York, 2013.
W. F. Klostermeyer and J. L. Goldwasser, Total perfect codes in grid graphs, Bull. Inst. Combin. Appl. 46 (2006) 61--68.
J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37 (2001), no. 4, 213--219.
N. Soltankhah, On the total domination subdivision numbers of grid graphs, Int. J. Contemp. Math. Sci. 5 (2010), no. 49-52, 2419--2432.
N. Soltankhah, Results on total domination and total restrained domination in grid graphs, Int. Math. Forum 5 (2010), no. 5-8, 319--332.