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**

[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.

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.

Articles in Press, Accepted Manuscript

Available Online from 25 October 2022