Chromatic Transversal Roman Domination in Graphs

Document Type : Original paper

Author

Department of Mathematics, D.B. Jain College, Chennai - 600 097, India

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.  https://doi.org/10.1137/070699688
[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, Article ID: 1450038.  https://doi.org/10.1142/S1793830914500384
[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.  https://doi.org/10.1016/j.akcej.2019.12.001
[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.  https://doi.org/10.3906/mat-1710-97
[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.  https://doi.org/10.1016/j.disc.2003.06.004
[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.  https://doi.org/10.7151/dmgt.1178
[14] M.A. Henning, Defending the Roman empire from multiple attacks, Discrete Math. 271 (2003), no. 1-3, 1101–115. https://doi.org/10.1016/S0012-365X(03)00040-2
[15] N. Jafari Rad and H. Rahbani, A Nordhaus–Gaddum bound for Roman domination, Discrete Math. Algorithms Appl. 11 (2019), no. 5, Article ID: 1950055.  https://doi.org/10.1142/S1793830919500551
[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.  http://dx.doi.org/10.7151/dmgt.1635
[19] H.B. Merouane, M. Haddad, M. Chellali, and H. Kheddouci, Dominated colorings of graphs, Graphs Combin. 31 (2015), no. 3, 713–727.  https://doi.org/10.1007/s00373-014-1407-3
[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.  https://doi.org/10.1080/09720529.2012.10698378
[25] P. Roushini Leely Pushpam and S. Padmapriea, Restrained Roman domination in graphs, Trans. Comb. 4 (2015), no. 1, 1–17.  https://doi.org/10.22108/toc.2015.4395
[26] P. Roushini Leely Pushpam and T.N.M. Malini Mai, Global Roman domination in graphs, Discrete Appl. Math. 200 (2016), 176–185.  https://doi.org/10.1016/j.dam.2015.07.014
[27] I. Stewart, Defend the Roman empire!, Scientific American 281 (1999), no. 6, 136–138.
Communications in Combinatorics and Optimization
Volume 9, Issue 1
March 2024
Pages 51-66

Files

Share

How to cite

Statistics