Geodesic
Roman bondage in graphs
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 4, pp. 763-773

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: domination, Roman domination, Roman bondage number 
@article{DMGT_2011_31_4_a9,
     author = {Rad, Nader and Volkmann, Lutz},
     title = {Roman bondage in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {763--773},
     publisher = {mathdoc},
     volume = {31},
     number = {4},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a9/}
}
TY  - JOUR
AU  - Rad, Nader
AU  - Volkmann, Lutz
TI  - Roman bondage in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 763
EP  - 773
VL  - 31
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a9/
LA  - en
ID  - DMGT_2011_31_4_a9
ER  - 
%0 Journal Article
%A Rad, Nader
%A Volkmann, Lutz
%T Roman bondage in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 763-773
%V 31
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a9/
%G en
%F DMGT_2011_31_4_a9
Rad, Nader; Volkmann, Lutz. Roman bondage in graphs. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 4, pp. 763-773. http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a9/