Roman Domination on Acyclic Permutation Graphs

Angshu Kumar Sinha, Sachchidanand Mishra, Akul Rana, Anita Pal

Abstract


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.

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.26713%2Fjims.v9i3.772

eISSN 0975-5748; pISSN 0974-875X