DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 31(4) (2011) 763-773
DOI: 10.7151/dmgt.1578

Roman Bondage in Graphs

Nader Jafari Rad

Department of Mathematics
Shahrood University of Technology
Shahrood, Iran
and
School of Mathematics
Institute for Research in Fundamental Sciences (IPM)
P.O. Box 19395--5746, Tehran, Iran

Lutz Volkmann

Lehrstuhl II für Mathematik
RWTH Aachen University
Templergraben 55, D--52056 Aachen, Germany

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 bR(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

2010 Mathematics Subject Classification: 05C69.

References

[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.
[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.
[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.
[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.
[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.
[6]T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
[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.
[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.
[10]D.B. West, Introduction to Graph Theory, (2nd edition) (Prentice Hall, USA, 2001).

Received 14 June 2010
Revised 23 November 2010
Accepted 23 November 2010