×

On the Roman bondage number of planar graphs. (English) Zbl 1235.05105

Summary: A Roman dominating function on a graph \(G\) is a function \(f : V(G) \rightarrow \{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)) = \sum_{u\in V(G)} f(u)\). The Roman domination number, \(\gamma_{R}(G)\), of \(G\) is the minimum weight of a Roman dominating function on \(G\). The Roman bondage number \(b_{R}(G)\) of a graph \(G\) with maximum degree at least two is the minimum cardinality of all sets \(E' \subseteq E(G)\) for which \(\gamma_{R}(G-E') > \gamma_{R}(G)\). In this paper we present different bounds on the Roman bondage number of planar graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauer D., Harary F., Nieminen J., Suffel C.L.: Domination alteration sets in graphs. Discrete Math. 47, 153–161 (1983) · Zbl 0524.05040 · doi:10.1016/0012-365X(83)90085-7
[2] Carlson K., Develin M.: On the bondage number of planar and directed graphs. Discrete Math. 306, 820–826 (2006) · Zbl 1122.05045 · doi:10.1016/j.disc.2006.02.008
[3] Cockayne E.J., Dreyer P.M. Jr, Hedetniemi S.M., Hedetniemi S.T.: Roman domination in graphs. Discrete Math. 278, 11–22 (2004) · Zbl 1036.05034 · doi:10.1016/j.disc.2003.06.004
[4] Dunbar J.E., Haynes T.W., Teschner U., Volkmann L.: Bondage, insensitivity, and reinforcement. In: Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (eds) Domination in Graphs: Advanced Topics, pp. 471–489. Marcel Dekker, New York (1998) · Zbl 0894.05025
[5] Fink J.F., Jacobson M.S., Kinch L.F., Roberts J.: The bondage number of a graph. Discrete Math. 86, 47–57 (1990) · Zbl 0745.05056 · doi:10.1016/0012-365X(90)90348-L
[6] Fischermann M., Rautenbach D., Volkmann L.: Remarks on the bondage number of planar grahs. Discrete Math. 260, 57–67 (2003) · Zbl 1009.05104 · doi:10.1016/S0012-365X(02)00449-1
[7] Hartnell B.L., Rall D.F.: Bounds on the bondage number of a graph. Discrete Math. 128, 173–177 (1994) · Zbl 0796.05051 · doi:10.1016/0012-365X(94)90111-2
[8] Haynes T.W., Hedetniemi S.T., Slater P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998) · Zbl 0890.05002
[9] Jafari Rad, N., Volkmann, L.: Roman bondage in graphs. Submitted for publication (2009) · Zbl 1255.05137
[10] Kang L., Yuan J.: Bondage number of planar graphs. Discrete Math. 222, 191–198 (2000) · Zbl 0961.05055 · doi:10.1016/S0012-365X(99)00405-7
[11] ReVelle C.S., Rosing K.E.: Defendens imperium romanum: a classical problem in military strategy. Am. Math. Mon. 107, 585–594 (2000) · Zbl 1039.90038 · doi:10.2307/2589113
[12] Stewart I.: Defend the Roman Empire!. Sci. Am. 281, 136–139 (1999) · doi:10.1038/scientificamerican1299-136
[13] Teschner U.: New results about the bondage number of a graph. Discrete Math. 171, 249–259 (1997) · Zbl 0881.05067 · doi:10.1016/S0012-365X(96)00007-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.