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

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

Keywords Roman domination number; Roman bondage number; tree

Citation: Fu-Tao Hu, Xing Wei Wang, Ning Li. Characterization of trees with Roman bondage number 1. AIMS Mathematics, 2020, 5(6): 6183-6188. doi: 10.3934/math.2020397

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.

 

Reader Comments

your name: *   your email: *  

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

Download full text in PDF

Export Citation

Copyright © AIMS Press All Rights Reserved