The Total Bondage Numbers And Efficient Total Dominations Of Vertex-Transitive Graphs

In this dissertation,we mainly consider non-empty simple graphs.In general,the graphs that we are talking about include both directed graphs and undirected graphs.In graph theory,there is no definite way to specify the symbol of a graph.Generally,we use G =(V,E)to represent a graph,in which V = V(G)represents the vertex set of G,E = E(G)represents the edge set of G.Vertices pair(u,v)represents an edge from the vertex u to the vertex v.Notice that if(u,v),(v,u)?E,then these two directed edges can be considered as an undirected edge,represents by uv.Let G be a directed graph.If for any edge(u,v)in E,there has(v,u)?E,then G is called to be an undirected graph.Let D be a vertex subset of graph G,if for any vertex v not in the D,there exists a vertex in D such that(u,v)? E,then D is called to be a dominating set of G.The domination number of graph G,defined by ?(G),is the minimum cardinality of a dominating set.The total domination set of graph G with all vertices has in degree none zero is a subset S(?)V(G)such that for any vertex v ? V(G)there exists a vertex in S such that(u,v)? E.The total domination number of graph G is the minimum cardinality of a total dominating set,usually denoted by ?_t(G).The bondage number of a graph G,denoted by b(G),is the minimum number of edges whose delete results in larger domination number.The total bondage number of a graph G with all vertices has in degree none zero,denoted by b_t(G),is the minimum number of edges whose delete results in larger domination number.We establish an exact lower bound of the total bondage number for vertex-transitive graphs(usually lower bound is more difficult than upper bound),and we also get an upper bound of the total bondage number for the regular graph by studying the relationship between the total bondage number and the effective total domination number.If a graph G contains an efficient total dominating set,then tight upper and lower bounds are given when G is undirected,exact value is determined when G is directed.As application,we also study some cyclic graphs,harary graphs,mesh networks,and obtain their total bondage numbers by consider-ing their efficient total domination set.In addition,for some special graphs,such as the hypercube,also get the upper and lower bounds of their total bondage numbers.