A Note on the Roman Bondage Number of Planar Graphs

作者：Akbari Saieed; Khatirinejad Mahdad^*; Qajar Sahar

来源：Graphs and Combinatorics, 2013, 29(3): 327-331.

DOI：10.1007/s00373-011-1129-8

• Roman bondage number
• Roman domination number

A Roman dominating function on a graph G = (V(G), E(G)) is a labelling satisfying the condition that every vertex with label 0 has at least a neighbour with label 2. The Roman domination number gamma (R) (G) of G is the minimum of over all such functions. The Roman bondage number b (R) (G) of G is the minimum cardinality of all sets for which gamma (R) (G \ E) %26gt; gamma (R) (G). Recently, it was proved that for every planar graph P, b (R) (P) a parts per thousand currency sign Delta(P) + 6, where Delta(P) is the maximum degree of P. We show that the Roman bondage number of every planar graph does not exceed 15 and construct infinitely many planar graphs with Roman bondage number equal to 7.

• 出版日期2013-5