On The Bondage Numbers Of Graphs

Let G=(V, E) be a graph. A subset D (?) V is a dominating set if every vertex not in D is adjacent to a vertex in D. For a graph G without isolated vertices, a dominating set D is called a total dominating set if every vertex in D is adjacent to a vertex in D. The domination (resp. total domination) number of G is the smallest cardinality of a dominating (resp. total dominating) set of G. The bondage (resp. total bondage) number of a nonempty graph G (resp. without isolated vertices) is the smallest number of edges whose removal from G results in a graph with larger domination (resp. total domination) number of. The reinforcement (resp. total reinforcement) number of G (resp. without isolated vertices) is the smallest number of edges whose addition to G results in a graph with smaller domination (resp. total domination) number.A Roman dominating function on graph G is a function f:Vâ†'{0,1,2} such that every vertex v with f(v)=0has at least one neighbor u with f(u)=2. The weight of a Roman dominating function is the value f(V)=∑u∈vf(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number, denoted by γR(G). The Roman bondage number bR (G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E’(?) E(G) for which γR(G-E’)> γR(G).In this dissertation, we mainly focus on the problems of the bondage number of a graph. Firstly, this thesis shows that the decision problems for determining the (total) bondage numbers and (total) reinforcement numbers for general graphs are all NP-hard.Secondly, this dissertation considers the bondage and total bondage numbers of grid graphs and have the following conclusions, where Gn,m=Pn×Pm be the Cartesian product of two paths Pn and Pm, and A={1,2,3,5,6,9}. b(G2,2)=3,b(G3,2)=2ï¼› b(G5,4)=b(G9,4)=3,b(G6,4)=2,and b(Gn,4)=1for n(?)A;In the same time,this thesis determines that b(G)=n-3for an(n-3)-regular graph G of order n.Finglly,this dissertation concentrates on the Roman bondage number of a graph. It shows that the decision problem for determining the Roman bondage number is NP-hard even for bipartite graphs,some bounds are gotten for Roman bondage number,and the exact values of Roman bondage number for complete t-partite graphs and(n-3)-regular graphs of order n are obtained.