| The study of domination in graphs is an important research area,perhaps also the fastest-growing area within graph theory.Research on domination in graphs has not only important theoretical signification,but also varied application in such fields as computer science,communication networks,coding theory, operations search,and social sciences.Domination and its variations have been extensively studied.In this thesis,we study three variations of the classical domination:total restrained domination,total outer-connected domination and outer-connected domination. The thesis is organized as follows.In Chapter 2,we discuss the bounds on total restrained domination number and characterize some extremal graphs for inequalities involving this domination parameter.If there is a total restrained dominating set for a graph G,thenγtr(G)≤n or n-2.Firstly,we constructively characterize those trees which have the total restrained domination number with n or n - 2,also general graphs and clawfree graphs which have the total restrained domination number with n.Secondly, we discuss the total restrained domination number on claw-free graphs.For many domination-related parameters,its bounds(in terms of order and maximum degree of a graph) have been investigated.For the total restrained domination number, Henning et al.have proved:if G is a connected graph with minimum degree at least 2,thenγtr(G)≤n-Δ/2-1.Restricting our attention on claw-free graphs,we improve this result and prove:if G is a connected claw-free graph with minimum degree at least 2,thenγtr(G)≤n -Δ+1.Simultaneously,we also characterize those extremal graphs achieving the upper bound.Finally,for cubic graphs,by use of the map and analytical method,we establish an upper bound and a lower bound for total restrained domination number and constructively characterize those graphs achieving the lower bound.Restricting our attention on claw-free graphs, we prove that the total restrained and total domination number is equal for clawfree cubic graphs.This indicates that some results for the total domination also hold for the total restrained domination.In Chapter 3,we mainly discuss the total outer-connected domination number which is recently introduced by J.Cyman.We establish the lower and upper bound on the sum of the restrained domination number of a graph and its complement graph(which is also called the Nordhaus-Gaddum-type inequality in Graph Theory) and characterize those extremal graphs achieving those bounds.In Chapter 4,by the general rule which is followed when a new dominationrelated parameter is put forward,naturally we introduce the concept of outer-connected domination and investigate its extremal graphs,bounds and complexity. Obviously for arbitrary graphs G,we haveγoc(G)≤n(whereγoc(G) denotes the outer-connected domination number of G).Firstly,we characterize constructively those extremal graphs which have the outer-connected domination number with n,n-1 or n-2 and establish the lower and upper bounds on the sum of outer-connected domination number of a graph and its complement graph.Secondly,we consider the outer-connected domination number for trees.In terms of maximum degree and cardinality of a tree,we obtain two lower bounds and characterize the extremal trees achieving those bounds.Finally,we prove that the decision problem for the outer-connected domination is NP-complete. |
