AIMS Mathematics, 2020, 5(6): 6183-6188. doi: 10.3934/math.2020397

Research article

Export file:

Format

• RIS(for EndNote,Reference Manager,ProCite)
• BibTex
• Text

Content

• Citation Only
• Citation and Abstract

Characterization of trees with Roman bondage number 1

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

## Abstract    Full Text(HTML)    Figure/Table    Related pages

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$.
Figure/Table
Supplementary
Article Metrics

# References

1. S. Akbari, M. Khatirinejadand, S. Qajar, A note on Roman bondage number of planar graphs, Graph. Combinator., 29 (2013), 327-331.

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.

5. J. F. Fink, M. S. Jacobson, L. F. Kinch, et al. The bondage number of a graph, Discrete Math., 86 (1990), 47-57.

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.

10. N. J. Rad, L. Volkmann, On the Roman bondage number of planar graphs, Graph. Combinator., 27 (2011), 531-538.

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.

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.