Discussiones Mathematicae Graph Theory 31(4) (2011)
763-773
DOI: https://doi.org/10.7151/dmgt.1578
Roman Bondage in Graphs
Nader Jafari Rad
Department of Mathematics | Lutz Volkmann
Lehrstuhl II für Mathematik |
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
Close