# Roman bondage in graphs

Nader Jafari Rad; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2011)

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

## Access Full Article

top## Abstract

top## How to cite

topNader 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] 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] 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] 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] 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] 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] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
- [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] I. Stewart, Defend the Roman Empire!, Sci. Amer. 281 (1999) 136-139, doi: 10.1038/scientificamerican1299-136.
- [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] D.B. West, Introduction to Graph Theory, (2nd edition) (Prentice Hall, USA, 2001).

## Citations in EuDML Documents

top## NotesEmbed ?

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