Characterization of trees with Roman bondage number 1

Fu-Tao Hu; Xing Wei Wang; Ning Li; Fu-Tao Hu; Xing Wei Wang; Ning Li

doi:10.3934/math.2020397

AIMS Mathematics

2020, Volume 5, Issue 6: 6183-6188. doi: 10.3934/math.2020397

Previous Article Next Article

Research article

Characterization of trees with Roman bondage number 1

School of Mathematical Sciences, Anhui University, Hefei, 230601, P. R. China

Received: 19 May 2020 Accepted: 14 July 2020 Published: 31 July 2020
MSC : 05C69

Let $G = (V, E)$ be a simple undirected graph. A Roman dominating function on $G$ is a function $f: V\to \{0, 1, 2\}$ satisfying the condition that every vertex $u$ with $f(u) = 0$ is adjacent to at least one vertex $v$ with $f(v) = 2$. The weight of a Roman dominating function is the value $f(G) = \sum_{u\in V} f(u)$. The Roman domination number of $G$ is the minimum weight of a Roman dominating function on $G$. The Roman bondage number of a nonempty graph $G$ is the minimum number of edges whose removal results in a graph with the Roman domination number larger than that of $G$. Rad and Volkmann [9] proposed a problem that is to determine the trees $T$ with Roman bondage number $1$. In this paper, we characterize trees with Roman bondage number $1$.
- Roman domination number,
- Roman bondage number,
- tree
Citation: Fu-Tao Hu, Xing Wei Wang, Ning Li. Characterization of trees with Roman bondage number 1[J]. AIMS Mathematics, 2020, 5(6): 6183-6188. doi: 10.3934/math.2020397

Related Papers:

Abstract

Let $G = (V, E)$ be a simple undirected graph. A Roman dominating function on $G$ is a function $f: V\to \{0, 1, 2\}$ satisfying the condition that every vertex $u$ with $f(u) = 0$ is adjacent to at least one vertex $v$ with $f(v) = 2$. The weight of a Roman dominating function is the value $f(G) = \sum_{u\in V} f(u)$. The Roman domination number of $G$ is the minimum weight of a Roman dominating function on $G$. The Roman bondage number of a nonempty graph $G$ is the minimum number of edges whose removal results in a graph with the Roman domination number larger than that of $G$. Rad and Volkmann [9] proposed a problem that is to determine the trees $T$ with Roman bondage number $1$. In this paper, we characterize trees with Roman bondage number $1$.

References

[1]	S. Akbari, M. Khatirinejadand, S. Qajar, A note on Roman bondage number of planar graphs, Graph. Combinator., 29 (2013), 327-331. doi: 10.1007/s00373-011-1129-8
[2]	A. Bahremandpour, F. T. Hu, S. M. Sheikholeslami, et al. Roman bondage number of a graph, Discrete Math. Algorithm. Appl., 5 (2013), 1-15.
[3]	X. G. Chen, A note on the double Roman domination number of graphs, Czech. Math. J., 70 (2020), 205-212.
[4]	E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi, et al. Roman domination in graphs, Discrete Math., 278 (2004), 11-22. doi: 10.1016/j.disc.2003.06.004
[5]	J. F. Fink, M. S. Jacobson, L. F. Kinch, et al. The bondage number of a graph, Discrete Math., 86 (1990), 47-57. doi: 10.1016/0012-365X(90)90348-L
[6]	A. Hansberg, N. J. Rad, L. Volkmann, Vertex and edge critical Roman domination in graphs, Utliltas Math., 92 (2013), 73-88.
[7]	T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, New York: Marcel Dekker, 1998.
[8]	T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in graphs: Advanced topics, New York: Marcel Dekker, 1998.
[9]	N. J. Rad, L. Volkmann, Roman bondage in graphs, Discuss. Math. Graph T., 31 (2011), 763-773. doi: 10.7151/dmgt.1578
[10]	N. J. Rad, L. Volkmann, On the Roman bondage number of planar graphs, Graph. Combinator., 27 (2011), 531-538. doi: 10.1007/s00373-010-0978-x
[11]	N. J. Rad, L. Volkmann, Changing and unchanging the Roman domination number of a graph, Utliltas Math., 89 (2012), 79-95.
[12]	V. Samodivkin, On the Roman bondage number of graphs on surfaces, Int. J. Graph Theory Appl., 1 (2015), 67-75.
[13]	I. Stewart, Defend the Roman empire, Sci. Am., 281 (1999), 136-138. doi: 10.1038/scientificamerican1299-136
[14]	J. M. Xu, Theory and application of graphs, Dordrecht/Boston/London: Kluwer Academic Publishers, 2003.
[15]	J. M. Xu, On bondage numbers of graphs: A survey with some comments, Int. J. Combinator., 2013 (2013), 1-34.

Reader Comments

Your name:*

Email:*
© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)