Dominator semi strong color partition in graphs

Abstract

Let $G$ =$(V,E)$ be a simple graph. A subset $S$ is said to be Semi-Strong if for every vertex $v$ in $V$, $|N\left(v\right)\cap S|\le 1$, or no two vertices of $S$ have the same neighbour in $V$, that is, no two vertices of $S$ are joined by a path of length two in $V$. The minimum cardinality of a semi-strong partition of $G$ is called the semi-strong chromatic number of $G$ and is denoted by ${\chi }_{s}G$. A proper colour partition is called a dominator colour partition if every vertex dominates some colour class, that is , every vertex is adjacent with every element of some colour class. In this paper, instead of proper colour partition, semi-strong colour partition is considered and every vertex is adjacent to some class of the semi-strong colour partition.Several interesting results are obtained.

Keywords

• Dominator coloring
• semi strong color partition
• semi-strong coloring

References

1. Arumugam, S., Bagga, J., Chandrasekar, K.R., On dominator colorings in graphs, Proc. Indian Acad. Sci. (Math Sci.), 122(4) (2012), 561–578.
2. Berge, C., Graphs and Hyper Graphs, North Holland, Amsterdam, 1973.
3. Chartrand, G., Salehi, E., Zhang, P., The partition dimension of a graph, Aequationes Math., 59 (2000), 45-54. https://doi.org/10.1007/PL00000127
4. Chellali, M., Maffray, F., Dominator colorings in some classes of graphs, Graphs and Combinatorics, 28 (2012), 97–107. https://doi.org/10.1007/s00373-010-1012-z
5. Chitra, S., Gokilamani and Swaminathan, V., Color Class Domination in Graphs, Mathematical and Experimental Physics, Narosa Publishing House, 2010, 24–28.
6. Gera, R., On dominator coloring in graphs, Graph Theory Notes, N.Y., 52 (2007), 25–30.
7. Gera, R., Horton, S., Rasmussen, C., Dominator colorings and safe clique partitions, Congr. Num., 181 (2006), 19-32.
8. Harary, F., Graph Theory, Addison-Wesley Reading, MA, 1969.

9. Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Fundamentals of Domination in Graphs, Marcel Dekker Inc., 1998.
10. Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Domination in Graphs: Advanced Topics, Marcel Dekker Inc., 1998.
11. Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R., McRae, A.A., Blair, J.R.S., Dominator Colorings of Graphs, 2006, Preprint.
12. Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R., McRae, A.A., Wallis, C.K., Dominator partitions of graphs, J. Combin. Systems Sci., 34(1-4) (2009), 183-192.
13. Jothilakshmi, G., Pushpalatha, A.P., Suganthi, S., Swaminathan, V., (k,r)-Semi strong chromatic number of a graph, International Journal of Computer Applications, 21(2) (2011), 7-11.
14. Kazemi, A.P., Total dominator chromatic number of a graph, Trans. Comb., 4 (2015), 57-68.
15. Kazemi, A.P., Total dominator coloring in product graphs, Util. Math., 94 (2014), 329-345.
16. Kazemi, A.P., Total dominator chromatic number and Mycieleskian graphs, Util. Math., 103 (2017), 129-137.
17. Merouane, H.B., Haddad, M., Chellali, M., Kheddouci, H., Dominated colorings of graphs, Graphs and Combinatorics, 31 (2015), 713-727. https://doi.org/10.1007/s00373-014-1407-3
18. Sampathkumar, E., Pushpa Latha, L., Semi-strong chromatic number of a graph, Indian Journal of Pure and Applied Mathematics, 26(1) (1995), 35-40.
19. Sampathkumar, E., Venkatachalam, C.V., Chromatic partition of a graph, Discrete Mathematics, 74 (1989), 227–239. https://doi.org/10.1016/S0167-5060(08)70311-X
20. Venkatakrishnan, Y.B., Swaminathan,V., Color class domination number of middle graph and center graph of K1,n, Cn, Pn, Advanced Modeling and Optimization, (12) (2010), 233–237.
21. Venkatakrishnan, Y.B., Swaminathan, V., Color class domination numbers of some classes of graphs, Algebra and Discrete Mathematics, 18(2) (2014), 301-305.