Independent Italian bondage of graphs

Document Type : Original paper

Authors

1 Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China

2 Azarbaijan Shahid Madani University

3 Department of Mathematics Prince Sattam bin Abdulaziz University Alkharj 11991, Saudi Arabia

4 RWTH Aachen University

Abstract

An independent Italian dominating function (IID-function) on a graph $G$ is a function $f:V(G)\rightarrow\{0,1,2\}$ satisfying the conditions that (i) $\sum_{u\in N(v)}f(u)\geq2$ when $f(v)=0$, and (ii) the set of all vertices assigned non-zero values under $f$ is independent. The weight of an IID-function is the sum of its function values over all vertices, and the independent Italian domination number $i_{I}(G)$ of $G$ is the minimum weight of an IID-function on $G$. In this paper, we initiate the study of the independent Italian bondage number $b_{iI}(G)$ of a graph $G$ having at least one component of order at least three, defined as the smallest size of a set of edges of $G$ whose removal from $G$ increases $i_{I}(G)$. We show that the decision problem associated with the independent Italian bondage problem is NP-hard for arbitrary graphs. Moreover, various upper bounds on $b_{iI}(G)$ are established as well as exact values on it for some special graphs. In particular, for trees $T$ of order at least three, it is shown that $b_{iI}(T)\leq2$.

Keywords

Main Subjects

References

[1] A. Bahremandpour, F.T. Hu, S.M. Sheikholeslami, and J.M. Xu, On the Roman bondage number of a graph, Discrete Math. Algorithms Appl. 5 (2013), no. 1, Article ID: 1350001.
[2] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A.A. McRae, Roman ${2}$-domination, Discrete Appl. Math. 204 (2016), 22–28.
[3] J.F. Fink, M.S. Jacobson, L.F. Kinch, and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990), no. 1-3, 47–57.
[4] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completness, Freeman, San Francisco, 1979.
[5] T.W. Haynes, S.T. Hedetniemi, and P.J. Salter, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[6] J. Hou and G. Liu, A bound on the bondage number of toroidal graphs, Discrete Math. Algorithms Appl. 4 (2012), no. 3, Article ID: 1250046.
[7] N. Jafari Rad, H.R. Maimani, M. Momeni, and F.R. Mahid, On the double Roman bondage numbers of graphs, Discrete Math. Algorithms Appl. 14 (2022), no. 8, Article ID: 2250046.
[8] N. Jafari Rad and L. Volkmann, Roman bondage in graphs, Discuss. Math. Graph Theory 31 (2011), no. 4, 763–773.
[9] J. Lyle, Regular graphs with large Italian domatic number, Commun. Comb. Optim. 7 (2022), no. 2, 257–271.
[10] A. Moradi, D.A. Mojdeh, and O. Sharifi, Roman {2}-bondage number of a graph, Discuss. Math. Graph Theory 40 (2020), no. 1, 255–268.
[11] A. Rahmouni and M. Chellali, Independent Roman ${2}$-domination in graphs, Discrete Appl. Math. 236 (2018), 408–414.
[12] L. Volkmann, The Italian domatic number of a digraph, Commun. Comb. Optim. 4 (2019), no. 1, 61–70.
[13] W. Zhao and H. Zhang, The bondage number of the strong product of a complete graph with a path and a special starlike tree, Discrete Math. Algorithms Appl. 8 (2016), no. 1, Article ID: 1650006.
Communications in Combinatorics and Optimization
Volume 8, Issue 4
December 2023
Pages 649-664

Files

Share

How to cite

Statistics