آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,550 |
| تعداد مشاهده مقاله | 1,643,368 |
| تعداد دریافت فایل اصل مقاله | 1,540,322 |
Independent Italian bondage of graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 4، دوره 8، شماره 4، اسفند 2023، صفحه 649-664 اصل مقاله (471.02 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2023.28662.1657 | ||
| نویسندگان | ||
| Saeed Kosari* 1؛ Jafar Amjadi* 2؛ Aysha Khan3؛ Lutz Volkmann4 | ||
| 1Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China | ||
| 2Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran | ||
| 3Department of Mathematics Prince Sattam bin Abdulaziz University Alkharj 11991, Saudi Arabia | ||
| 4RWTH Aachen University | ||
| چکیده | ||
| 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$. | ||
| کلیدواژهها | ||
| Independent Italian dominating function؛ independent Italian domination number؛ independent Italian bondage number | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 698 تعداد دریافت فایل اصل مقاله: 1,051 |
||