Roman bondage in graphs

Nader Jafari Rad; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 4, page 763-773
  • ISSN: 2083-5892

Abstract

top
A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value f ( V ( G ) ) = ∑ u ∈ V ( G ) f ( u ) . The Roman domination number, γ R ( G ) , of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage b R ( G ) of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G) for which γ R ( G - E ' ) > γ R ( G ) . We determine the Roman bondage number in several classes of graphs and give some sharp bounds.

How to cite

top

Nader Jafari Rad, and Lutz Volkmann. "Roman bondage in graphs." Discussiones Mathematicae Graph Theory 31.4 (2011): 763-773. <http://eudml.org/doc/270940>.

@article{NaderJafariRad2011,
abstract = {A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f(V(G)) = ∑_\{u ∈ V(G)\}f(u)$. The Roman domination number, $γ_R(G)$, of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_R(G)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G) for which $γ_R(G -E^\{\prime \}) > γ_R(G)$. We determine the Roman bondage number in several classes of graphs and give some sharp bounds.},
author = {Nader Jafari Rad, Lutz Volkmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; Roman domination; Roman bondage number},
language = {eng},
number = {4},
pages = {763-773},
title = {Roman bondage in graphs},
url = {http://eudml.org/doc/270940},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Nader Jafari Rad
AU - Lutz Volkmann
TI - Roman bondage in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 4
SP - 763
EP - 773
AB - A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f(V(G)) = ∑_{u ∈ V(G)}f(u)$. The Roman domination number, $γ_R(G)$, of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_R(G)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G) for which $γ_R(G -E^{\prime }) > γ_R(G)$. We determine the Roman bondage number in several classes of graphs and give some sharp bounds.
LA - eng
KW - domination; Roman domination; Roman bondage number
UR - http://eudml.org/doc/270940
ER -

References

top
  1. [1] D. Bauer, F. Harary, J. Nieminen and C.L. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983) 153-161, doi: 10.1016/0012-365X(83)90085-7. Zbl0524.05040
  2. [2] E.J. Cockayne, P.M. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22, doi: 10.1016/j.disc.2003.06.004. Zbl1036.05034
  3. [3] J.E. Dunbar, T.W. Haynes, U. Teschner and L. Volkmann, Bondage, insensitivity, and reinforcement, in: T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998) 471-489. Zbl0894.05025
  4. [4] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47-57, doi: 10.1016/0012-365X(90)90348-L. Zbl0745.05056
  5. [5] B.L. Hartnell and D.F. Rall, Bounds on the bondage number of a graph, Discrete Math. 128 (1994) 173-177, doi: 10.1016/0012-365X(94)90111-2. Zbl0796.05051
  6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  7. [7] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer Math. Monthly 107 (2000) 585-594, doi: 10.2307/2589113. Zbl1039.90038
  8. [8] I. Stewart, Defend the Roman Empire!, Sci. Amer. 281 (1999) 136-139, doi: 10.1038/scientificamerican1299-136. 
  9. [9] U. Teschner, New results about the bondage number of a graph, Discrete Math. 171 (1997) 249-259, doi: 10.1016/S0012-365X(96)00007-6. Zbl0881.05067
  10. [10] D.B. West, Introduction to Graph Theory, (2nd edition) (Prentice Hall, USA, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.