On Roman Domination in Middle and Splitting Graphs

Abstract

For a graph G=(V,E), a Roman dominating function(RDF) is a function f:V→{0,1,2} having the property that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of an RDF ((w(f)) is the sum of assignments for all vertices. The minimum weight of an Roman dominating function on graph G is the Roman domination number, denoted by γ_R (G). In this paper, we study on this variant of the domination number for middle, splitting and Mycielski graphs of some special graphs.

Keywords

• Graph vulnerability
• domination
• Roman domination.

References

1. AYTAÇ, A. and TURACI, T. (2015). Strong Weak Domination in Complementary Prisms, Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications and Algorithms, 22(2), 85-96.
2. BERMUDO, S.,FERNAU, H.,SIGARRETTA, J. (2014). The Differential and the Roman Domination Number of a Graph, Appl. Anal. Discret. Math., 8, 155-171.
3. BLIDIA, M., BOUCHOU, A., CHELLALI, M. (2020). Extremal Graphs for a Bound on the Roman Domination Number, Discuss. Math. Graph Theory, 40, 771-785.
4. CHANG, G.J., HUANG, L., ZHU, X. (1999). Circular Chromatic Numbers of Mycielski’s Graphs, Descrete Math, 205, 23-37.
5. CHAMBERS, E.W., KINNERSLEY, B., PRINCE, N., WEST, D.B. (2009). Extermal Problems for Roman Domination, SIAM j. Discret Mathematics, 23(3) 1575-1586.
6. COCKAYNE, E.J., DREYER Jr, P.A., HEDETNIEMI, S.A. (2004). Roman Domination in Graphs, Discrete Mathematics, 11-22. HARARY, F. (1969). Graph Teory, In: Addition- Wesley Publishing Co. Reading, MA/Menlo Park, CA/London.
7. HARTSFIELD, N. and RINGEL, G. (1990). Pearls in Graph Theory, In: Academic Press, INC.
8. HAYNES, T.W., HEDETNIEMI, P.J., SLATER, P.J. (1998). Fundamentals of Domination in Graphs, Marcel Dekker, New York.

9. KARTAL, Z. and AYTAÇ, A. (2010). Semitotal Domination of Harary Graphs, Tbilisi Mathematical Journal, 3, 11-17.
10. LIU, C.H. and CHANG, G.J.(2012). Upper Bounds on Roman Domination numbers of Graphs, Discret. Math., 312, 1386-1391.
11. LIEDLOFF, M., KLOKS, T., LIU, J., PENG, S.L. (2008). Efficient Algorithms for Roman Domination on Some Classes of Graphs, Discret. Appl. Math., 156, 3400-3415.
12. MOJDEH, D.A., PARSIAN, A., MASOUMI, I. (2019). Strong Roman Domination Number of Complementary Prism Graphs, Turk. J. Math. Comput. Sci, 40-47.
13. RAMAKRISHNAN,(1988).MPhil-Thesis, Pondicherry University, Puducherry, India.
14. SAMPATHKUMAR, E. & WALİKAR, H.B. (1980). On the Splitting Graph of a Graph, The Karnataka University Journal Science, 25&26, 13-16.
15. STEWART, I. (1999). Defend the Roman Empire!, Sci. Ame., 281,136-139.
16. WEST, D.B. (2001). Introduction to Graph Theory, In: Pearson Education (Second Edition)
17. XING, H.M., CHEN, X., CHEN X.G. (2006). A Note on Roman Domination in Graphs, Discret. Math., 306, 3338-3340.