Research On Roman Bondage Number Of Trees

Domination theory is an important research area in graph theory,it has im-portant applications in Physics,Computer Science,Information Science,Chemistry and many other subjects.Let G=(V,E)be a graph and D(?)V.For each vertex not in D,if there exits a vertex in D adjacent with it,then D is called a dominat-ing set of G.The dominating set problem of a graph is NP-complete,there is no polynomial time to solve it.Since the many applications and big research difficulty of domination number,the domination theory obtained a lot of attention and rapid development.According to the actual application,different domination numbers are defined accordingly.The bondage number is a parameter to measure the vulnerabil-ity of the domination number of a graph,that is,the effect of the edge deletion on the domination number,is a parameter to measure the domination performance of a graph.The real network is not static,not only the natural environment and also human attacks can affect it.Therefore,it is meaningful to study the dynamic net-work model.This paper mainly studies the Roman bondage number corresponding to the Roman domination number of a graph.Roman dominating function comes from[Defend the Roman Empire.Scientific American,281(1999),136-139]which is published by Ian Stewart in 1999.In graph theory,let G=(V,E)is a simple nonempty undirected graph.The Roman dominating function f:V?{0,1,2} is a function such that for any vertex u and f(u)=0 there exits a vertex v adjacent with u and f(v)=2.The weight of Real function f:V?R is w(f)??u?V f(u),simply denote f(G)=w(f).The Roman domination number of a graph G is the weight of a minimum dominating function,denoted by ?R(G).The Roman bondage number,denoted by bR(G),of a graph G is the minimum number of edges whose removal results in a graph with the Roman domination number larger than that of G.In this thesis,we consider the Roman bondage number of a acyclic simple undirected graph which is a tree,denoted by T.Rad and Volkmann introduced Roman bondage number problems of graphs in[Roman bondage in graphs,Discus-siones Mathematicae Graph Theory,31(2011),763-773].They proved the Roman bondage number of a tree is no more than 3.At the end of the paper they proposed the following problem:Characterize trees with Roman bondage number 1,2,3.In this thesis,we gave a characterization of trees with Roman bondage number 1,we also discussed trees with Roman bondage number 3.