Chromatic Transversal Roman Domination in Graphs

Document Type : Original paper

Author

University of Madras

Abstract

For a graph $G$ with chromatic number $k$, a dominating set $S$ of $G$ is called a chromatic-transversal dominating set (ctd-set) if $S$ intersects every color class of any $k$-coloring of $G$.  The minimum cardinality of a ctd-set of $G$ is called the {\em chromatic transversal domination number} of $G$ and is denoted by $\gamma_{ct}(G)$.  A {\em Roman dominating function} (RDF) in a graph $G$ is a function $f : V(G) \to \{0, 1, 2\}$ satisfying the condition 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 a Roman dominating function is the value $w(f) = \sum_{u \in V} f(u)$.  The minimum weight of a Roman dominating function of a graph $G$ is called the {\em Roman domination number} of $G$ and is denoted by $\gamma_R(G)$.  The concept of {\em chromatic transversal domination} is extended to Roman domination as follows:   For a graph $G$ with chromatic number $k$, a {\em Roman dominating function} $f$ is called a {\em chromatic-transversal Roman dominating function} (CTRDF) if the set of all vertices $v$ with $f(v) > 0$ intersects every color class of any $k$-coloring of $G$.  The minimum weight of a chromatic-transversal Roman dominating function of a graph $G$ is called the {\em chromatic-transversal Roman domination number} of $G$ and is denoted by $\gamma_{ctR}(G)$.  In this paper a study of this parameter is initiated.

Keywords

Main Subjects

References

[1] S. Askari, D.A. Mojdeh, and E. Nazari, Total global dominator chromatic number of graphs, TWMS J. App. and Eng. Math. 12 (2022), no. 2, 650–661.
[2] E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009), no. 3, 1575–1586.
[3] G. Chartrand and L. Lesniak, Graphs and Digraphs, Chapman and Hall, CRC, 2005.
[4] M. Chellali and N. Jafari Rad, Trees with unique Roman dominating functions of minimum weight, Discrete Math. Algorithms Appl. 6 (2014), no. 3, ID: 1450038.
[5] M. Chellali and N. Jafari Rad, Roman domination stable graphs upon edge-addition, Util. Math. 96 (2015), 165–178.
[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.
[7] F. Choopani, A. Jafarzadeh, A. Erfanian, and D.A. Mojdeh, On dominated coloring of graphs and some Nordhaus–Gaddum-type relations, Turkish J. Math. 42 (2018), no. 5, 2148–2156.
[8] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[9] E.J. Cockayne, P.J.P. Grobler, W.R. Grundlingh, J. Munganga, and J.H. Van Vuuren, Protection of a graph, Util. Math. 67 (2005), 19–32.
[10] R. Gera, On dominator colorings in graphs, Graph Theory Notes of New York 52 (2007), 25–30.
[11] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[12] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York,
1998.
[13] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002), no. 2, 325–334.
[14] M.A. Henning, Defending the Roman empire from multiple attacks, Discrete Math. 271 (2003), no. 1-3, 101–115.
[15] N. Jafari Rad and H. Rahbani, A Nordhaus–Gaddum bound for Roman domination, Discrete Math. Algorithms Appl. 11 (2019), no. 5, ID: 1950055.
[16] N. Jafari Rad and L. Volkmann, Roman bondage in graphs, Discuss. Math. Graph Theory 31 (2011), no. 4, 763–773.
[17] N. Jafari Rad and L. Volkmann, Changing and unchanging the Roman domination number of a graph, Util. Math. 89 (2012), 79–95.
[18] H. Merouane and M. Chellali, On the dominator colorings in trees, Discuss. Math. Graph Theory 32 (2012), no. 4, 677–683.
[19] H.B. Merouane, M. Haddad, M. Chellali, and H. Kheddouci, Dominated colorings of graphs, Graphs Combin. 31 (2015), no. 3, 713–727.
[20] L.B. Michaelraj, S.K. Ayyaswamy, and S. Arumugam, Chromatic transversal domination in graphs, J. Comb. Math. Comb. Comput. 75 (2010), 33–40.
[21] C.S. ReVelle, Can you protect the Roman Empire?, Johns Hopkins Magazine 49 (1997), no. 2, 40.
[22] P. Roushini Leely Pushpam and T.N.M. Malini Mai, On efficient Roman dominatable graphs, J. Combin. Math. Combin. Comput. 67 (2008), 49–58.
[23] P. Roushini Leely Pushpam and T.N.M. Malini Mai, Edge Roman domination in graphs, J. Combin. Math. Combin. Comput. 69 (2009), 175–182.
[24] P. Roushini Leely Pushpam and T.N.M. Malini Mai, Roman domination in unicyclic graphs, J. Discrete Math. Sci. Crypt. 15 (2012), no. 4-5, 237–257.
[25] P. Roushini Leely Pushpam and S. Padmapriea, Restrained Roman domination in graphs, Trans. Comb. 4 (2015), no. 1, 1–17.
[26] P. Roushini Leely Pushpam and T.N.M. Malini Mai, Global Roman domination in graphs, Discrete Appl. Math. 200 (2016), 176–185.
[27] I. Stewart, Defend the Roman empire!, Scientific American 281 (1999), no. 6, 136–138.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 October 2022

Files

Share

How to cite

Statistics