Roman Domination on Acyclic Permutation Graphs
DOI:
https://doi.org/10.26713/jims.v9i3.772Abstract
A function \(f : V\rightarrow[0, 1, 2]\) is said to be Roman dominating function on a graph \(G=(V, E)\) if the function \(f\) satisfies the condition that every vertex \(u\) for which \(f(u)=0\) has at least one neighboring vertex \(v\) with \(f(v)=2\). The weight of a Roman dominating function is the value \(f(V)=\sum\limits_{v\in V}{f(v)}\). The Roman domination number of \(G\) is the minimum weight of a Roman dominating function and is denoted by \(\gamma_{R}(G)\). In this paper we study the Roman domination number on acyclic permutation graphs.Downloads
References
S.C. Barman, S. Mondal and M. Pal, An efficient algorithm to find next-to-shortest path on permutation graphs, Journal of Applied Mathematics and Computing 31 (2009), 369 – 384.
J.G. Chang, Algorithmic aspects of domination in graphs, in Handbook of Combinatorial Optimization (D.-Z. Du and P.M. Pardalos eds.), 3, 339 – 405 (1998).
E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Mathematics 278 (2004), 11 – 22.
E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi and A. McRae, Roman domination in graphs II, Manuscript.
E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, and A.A. McRae, The algorithmic complexity of Roman domination, Manuscript.
O. Favaron, H. Karamic, R. Khoeilar and S.M. Sheikholeslami, Note on the Roman domination number of a graph, Discrete Mathematics 309 (2009), 3447 – 3451.
T. Gallai, Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungaria 18 (1967), 25 – 66.
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York (1980).
A. Hansber and L. Volkmann, Upper bounds on the k-domination number and the k-Roman domination number, Discrete Applied Mathematics 157 (2009), 1634 – 1639.
T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker Inc., New York (1998).
T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker Inc., New York (1998).
M. Liedloffa, T. Kloks, J. Liub and S.L. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Applied Mathematics 156 (2008), 3400 – 3415.
C.H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Mathematics 312 (2012), 1386 – 1391.
S. Mondal, M. Pal and T.K. Pal, An optimal algorithm for finding depth-first spanning tree on permutation graphs, Korean Journal of Computational and Applied Mathematics 6 (1999), 493 – 500.
S. Mondal, M. Pal and T. Pal, Optimal sequential and parallel algorithms to compute a Steiner tree on permutation graphs, International Journal of Computer Mathematics 80 (2003), 937 – 943.
O. Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ. 38 (1962), AMS.
M. Pal, A parallel algorithm to generate all maximal independent sets on permutation graphs, International Journal of Computer Mathematics 67 (1998), 261 – 274.
A. Pnueli, A. Lempel and S. Even, Transitive Orientation of graphs and identifications of permutation graphs, Canad. J. Math. 23 (1971), 160 – 175.
A. Rana, A. Pal and M. Pal, Efficient algorithms to solve k-domination problem on permutation graphs, high performance networking, computing and communication systems, Communications in Computer and Information Science, Springer, Berlin ” Heidelberg, 163 (2011), 327 – 334.
A. Rana, A. Pal and M. Pal, The 2-neighborhood covering problem on permutation graphs, Advanced Modeling and Optimization 13 (2011), 463 – 476.
C.S. ReVelle and K.E. Rosing, Defendens imperium Roman: A classical problem in military strategy, Amer. Math. Monthly 107 (2000), 585 – 594.
A. Saha, M. Pal and T.K. Pal, An efficient PRAM algorithm for maximum-weight independent set on permutation graphs, Journal of Applied Mathematics and Computing 19 (2005), 77 – 92.
A.K. Sinha, A. Rana and A. Pal, The 2-tuple domination problem on trapezoid graphs, Annals of Pure and Applied Mathematics 7 (2014), 71 – 76.
A.K. Sinha, A. Rana and A. Pal, Signed star domination number on proper interval graphs, International Journal of Pure and Applied Mathematics 106 (2016), 123 – 129.
J.R. Spinrad, On comparability and permutation graphs, SIAM Journal of Computing 14 (1985), 658 – 670.
I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), 136 – 139.
H.M. Xing, X. Chen and X.G. Chen, A note on Roman domination in graphs, Discrete Mathematics 306 (2006), 3338 – 3340.
F. Xueliang, Y. Yuanshenga and J. Baoqi, Roman domination in regular graphs, Discrete Mathematics 309 (2009), 1528 – 1537.
Downloads
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
