Research article

Characterization of trees with Roman bondage number 1

  • 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$.

    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:

  • 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$.


    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2794) PDF downloads(163) Cited by(0)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog