1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Double Total Dominator Chromatic Number of Graphs

Published Online: 20 Oct 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 24 Oct 2019
Accepted: 29 Jul 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

In this paper, we introduce and study a new coloring problem of graphs called the double total dominator coloring. A double total dominator coloring of a graph G with minimum degree at least 2 is a proper vertex coloring of G such that each vertex has to dominate at least two color classes. The minimum number of colors among all double total dominator coloring of G is called the double total dominator chromatic number, denoted by χddt(G). Therefore, we establish the close relationship between the double total dominator chromatic number χddt(G) and the double total domination number γ×2,t(G). We prove the NP-completeness of the problem. We also examine the e ects on χddt(G) when G is modified by some operations. Finally, we discuss the χddt(G) number of square of trees by giving some bounds.

Keywords

MSC 2010

[1] M.O. Albertson, S. Grossman and R. Haas, Partial list colorings, Discrete Math. 214 (2000) 235–240. doi:10.1016/S0012-365X(99)00315-510.1016/S0012-365X(99)00315-5Search in Google Scholar

[2] S. Arumugam, K. Raja Chandrasekar, N. Misra, P. Geevarghese and S. Saurabh, Algorithmic aspects of dominator colorings in graphs, IWOCA 2011, Lecture Notes in Comput. Sci. 7056 (2011) 19–30. doi:10.1007/978-3-642-25011-8_210.1007/978-3-642-25011-8_2Search in Google Scholar

[3] H.M. Boumediene and M. Chellali, On the dominator colorings in trees, Discuss. Math. Graph Theory 32 (2012) 677–683. doi:10.7151/dmgt.163510.7151/dmgt.1635Search in Google Scholar

[4] O.V. Borodin, A.V. Kostochka and D.R. Woodall, Total colorings of planar graphs with large girth, European J. Combin. 19 (1998) 19–24. doi:10.1006/eujc.1997.015210.1006/eujc.1997.0152Search in Google Scholar

[5] I. Caragiannisa, C. Kaklamanisa and P. Persiano, Edge coloring of bipartite graphs with constraints, Theoret. Comput. Sci. 270 (2002) 361–399. doi:10.1016/S0304-3975(00)00400-X10.1016/S0304-3975(00)00400-XSearch in Google Scholar

[6] M. Chellali and F. Ma ray, Dominator colorings in some classes of graphs, Graphs Combin. 28 (2012) 97–107. doi:10.1007/s00373-010-1012-z10.1007/s00373-010-1012-zSearch in Google Scholar

[7] M. Chellali and L. Volkmann, Relations between the lower domination parameters and the chromatic number of a graph, Discrete Math. 274 (2004) 1–8. doi:10.1016/S0012-365X(03)00093-110.1016/S0012-365X(03)00093-1Search in Google Scholar

[8] G. Chen, A. Gyárfas and R.H. Schelp, Vertex colorings with a distance restriction, Discrete Math. 191 (1998) 65–82. doi:10.1016/S0012-365X(98)00094-610.1016/S0012-365X(98)00094-6Search in Google Scholar

[9] M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, 1979).Search in Google Scholar

[10] R. Gera, On dominator colorings in graphs, Graph Theory Notes N.Y. 52 (2007) 25–30.Search in Google Scholar

[11] R. Gera, On the dominator colorings in bipartite graphs, Fourth International Conference on Information Technology, IEEE (2007) 947–952. doi:10.1109/ITNG.2007.14210.1109/ITNG.2007.142Search in Google Scholar

[12] R. Gera, S. Horton and C. Rasmussen, Dominator colorings and safe clique partitions, Congr. Numer. 181 (2006) 19–32.Search in Google Scholar

[13] M. Haddad, L. Dekar and H. Kheddouci, A distributed strict strong coloring algorithm for broadcast applications in ad hoc networks, Proceedings of the 8th International Conference on New Technologies in Distributed Systems (Lyon, 2008).10.1145/1416729.1416759Search in Google Scholar

[14] M. Haddad and H. Kheddouci, A strict strong coloring of trees, Inform. Process. Lett. 109 (2009) 1047–1054. doi:10.1016/j.ipl.2009.06.01210.1016/j.ipl.2009.06.012Search in Google Scholar

[15] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).Search in Google Scholar

[16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).Search in Google Scholar

[17] M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009) 32–63. doi:10.1016/j.disc.2007.12.04410.1016/j.disc.2007.12.044Search in Google Scholar

[18] M.A. Henning and A.P. Kazemi, k-tuple total domination in graphs, Discrete Appl. Math. 158 (2010) 1006–1011. doi:10.1016/j.dam.2010.01.00910.1016/j.dam.2010.01.009Search in Google Scholar

[19] M.A. Henning and A.P. Kazemi, k-tuple total domination in cross product of graphs, J. Comb. Optim. 24 (2012) 339–346. doi:10.1007/s10878-011-9389-z10.1007/s10878-011-9389-zSearch in Google Scholar

[20] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013). doi:10.1007/978-1-4614-6525-610.1007/978-1-4614-6525-6Search in Google Scholar

[21] R. Kalaivani and D. Vijayalakshmt, A note on domination chromatic number of line graph and jump graph of some graphs, Commun. Fac. Sci. Univ. Ank. Ser. A1 Math. Stat. 68 (2019) 1350–1358. doi:10.31801/cfsuasmas.52957810.31801/cfsuasmas.529578Search in Google Scholar

[22] A.P. Kazemi, k-tuple total domination in complementary prisms, ISRN Discrete Math. 2011 (2011) ID 681274. doi:10.5402/2011/68127410.5402/2011/681274Search in Google Scholar

[23] A.P. Kazemi, Total dominator chromatic number in graphs, manuscript. arXiv:1307.7486 (math.CO).Search in Google Scholar

[24] D.D.-F. Liu, T-colorings graphs, Discrete Math. 101 (1992) 203–212. doi:10.1016/0012-365X(92)90603-D10.1016/0012-365X(92)90603-DSearch in Google Scholar

[25] T. Manjula and R. Rajeswari, Dominator chromatic number of some graphs, Inter-nat. J. Pure Appl. Math. 119 (2018) 787–795.Search in Google Scholar

[26] A. Mohammed Abid and T.R. Ramesh Rao, Dominator coloring of Mycielskian graphs, Australas. J. Combin. 73 (2019) 274–279.Search in Google Scholar

[27] I.E. Zverovich, A new kind of graph coloring, J. Algorithms 58 (2006) 118–133. doi:10.1016/j.jalgor.2005.02.00110.1016/j.jalgor.2005.02.001Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo