Independent roman $\{3\}$-domination

Document Type : Research Paper

Authors

1 Department of Computer Science and Engineering, SR University, Warangal - 506 371, India

2 Department of Computer Science and Engineering, National Institute of Technology, Warangal - 506 004, India

Abstract

Let $G$ be a simple, undirected graph. In this paper, we initiate the study of independent Roman $\{3\}$-domination. A function $g : V(G) \rightarrow \lbrace 0, 1, 2, 3 \rbrace$ having the property that $\sum_{v \in N_G(u)}^{} g(v) \geq 3$, if $g(u) = 0$, and $\sum_{v \in N_G(u)}^{} g(v) \geq 2$, if $g(u) = 1$ for any vertex $u \in V(G)$, where $N_G(u)$ is the set of vertices adjacent to $u$ in $G$, and no two vertices assigned positive values are adjacent is called an \textit{ independent Roman $\{3\}$-dominating function} (IR3DF) of $G$. The weight of an IR3DF $g$ is the sum $g(V) = \sum_{v \in V}g(v)$. Given a graph $G$ and a positive integer $k$, the independent Roman $\{3\}$-domination problem (IR3DP) is to check whether $G$ has an IR3DF of weight at most $k$. We investigate the complexity of IR3DP in bipartite and chordal graphs. The minimum independent Roman $\lbrace 3 \rbrace$-domination problem (MIR3DP) is to find an IR3DF of minimum weight in the input graph. We show that MIR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs. We also show that the domination problem and IR3DP are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MIR3DP.

Keywords

Main Subjects

References

[1] A. Rahmouni and M. Chellali, Independent Roman {2}-domination in graphs, Discrete Appl. Math., 236 (2018)
408–414.
[2] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput.,
85 (1990) 12–75.
[3] C. E. Leiserson, R. L. Rivest, T. H. Cormen and C. Stein, Introduction to algorithms, Second edition. MIT Press,
Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001.
[4] C. S. ReVelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer.
Math. Monthly, 107 (2000) 585–594.
[5] C. Padamutham and V. S. R. Palagiri, Complexity Aspects of Variants of Independent Roman Domination in
Graphs, Bull. Iranian Math. Soc., (2021) 1715–1735.
[6] C. Padamutham and V. S. R. Palagiri, Algorithmic aspects of Roman domination in graphs, J. Appl. Math. Comput.,
64 (2020) 89–102.
[7] C. Padamutham and V. S. R. Palagiri, Complexity of Roman {2}-domination and the double Roman domination
in graphs, AKCE Int. J. Graphs Comb., 17 (2020) 1081–1086.
[8] D. A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math., 283
(2020) 555–564.
[9] D. B. West, Introduction to Graph Theory, 2, Upper Saddle River: Prentice Hall, 2001.
[10] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Math.,
278 (2004) 11–22.
[11] F. Alizade, H. R. Maimani, L. P. Majd and M. R. Parsa, Roman {2}-domination in graphs and graph products,
(2017).
[12] M. Adabi, E. E. Targhi, N. J. Rad and M. S. Moradi, Properties of independent Roman domination in graphs,
Australas. J. Combin., 52 (2012) 11–18.
[13] M. Chellali and N. J. Rad, Strong equality between the Roman domination and independent Roman domination
numbers in trees, Discuss. Math. Graph T., 33 (2013) 337–346.
[14] M. Chlebik and J. Chlebı́ková, The complexity of combinatorial optimization problems on d-dimensional boxes,
SIAM J. Discret. Math., 21 (2007) 158–169.
[15] M. Ivanović, Improved mixed integer linear programing formulations for roman domination problem, Publ. de
l’Institut Math., 99 (2016) 51–58.
[16] M. Chellali, T. W. Haynes, S. T. Hedetniemi and A. A. McRae, Roman {2}-domination, Discrete Appl. Math., 204
(2016) 22–28.
[17] M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, A Series
of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979.
[18] M. Yannakakis, Node- and edge-deletion NP-complete problems, In Proceedings of the Tenth Annual ACM Sympo-
sium on Theory of Computing, STOC, New York, USA, (1978) 253–264.
[19] N. Jafari Rad and L. Volkmann, Roman domination perfect graphs, An. Stiint. Univ. Ovidius Constanta Ser. Mat.,
19 (2011) 167–174.
[20] N. Mahadev and U. Peled, Threshold graphs and related topics, Annals of Discrete Mathematics, 56, North-Holland
Publishing Co., Amsterdam, 1995.
[21] O. Favaron, H. Karami, R. Khoeilar and S. M. Sheikholeslami, On the Roman domination number of a graph,
Discrete Math., 309 (2009) 3447–3451.
[22] P. Wu, Z. Li, Z. Shao and S. M. Sheikholeslami, Trees with equal Roman {2}-domination number and independent
Roman {2}-domination number, RAIRO-Oper. Res., 53 (2019) 389–400.
[23] R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, Algorithms and computation, Lecture
Notes in Comput. Sci., Springer, Berlin, (2004) 871–883.
[24] T. W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of domination in graphs, Monographs and Textbooks in
Pure and Applied Mathematics, 208, Marcel Dekker, Inc., New York, 1998.
[25] T. W. Haynes, S. Hedetniemi and P. Slater, Domination in graphs: advanced topics, Marcel Dekker, 1997.

Files

Cited by

History

  • Receive Date: 31 March 2021
  • Revise Date: 23 October 2021
  • Accept Date: 31 October 2021
  • Published Online: 01 June 2022

Share

How to cite

Statistics