Research On Total Edge Domination And Semitotal Edge Domination Problems For Graphs

Domination theory is an important topic in graph theory,and have many applications in resource allocation,network routing,as well as in coding theory.We mainly focus on the edge-related domination problems.Let F be an edge subset of graph G.If every edge not in F is adjacent to some edge in F,then F is an edge dominating set of G.If every edge of G is adjacent to some edge in F,then F is called a total edge dominating set of G.If F is an edge dominating set such that every edge in F either is adjacent to some edge in F or shares a common neighbor edge with some edge in F,then F is said to be a semitotal edge dominating set.The minimum cardinality of an edge dominating set(resp.,a total edge dominating set,a semitotal edge dominating set)is the edge domination number(resp.,total domination number,semitotal edge domination number)of G.Clearly,edge domination number is no more than semitotal edge domination number,semitotal edge domination number is no more than total edge domination number and total edge domination number is no more than 2 times edge domination number.Adding an edge to a graph may change the total edge domination number.Hence,graph G is said to be a total edge domination edge addition stable graph if adding any edge cannot change the total edge domination number.In this paper,we mainly study the characterization of trees satisfying some conditions of edge domination parameters,the complexity and algorithm aspects of edge-related domination problems.In addition,we also study the total edge domination edge addition stable graphs problems.The paper divided into four chapters as follows:In Chapter 1,we first introduce some basic concepts and notations.Then we introduce the background and the development of the edge domination.At last,we outline the main results obtained in the following chapters.In Chapter 2,we first prove that the total edge domination problem in planar bipartite graph with maximum degree 3 is NP-complete,then we design a dynamic algorithm in linear time to calculate the total edge domination number of a tree.Next,we prove that in a bipartite graph with maximum degree 4 to decide whether edge domination number is equal to total edge domination number is NP-hard.Last,we character trees satisfying the edge domination number is equal to total edge domination number and total edge domination number is equal to 2 times edge domination number,respectively.In Chapter 3,we first design a dynamic algorithm in linear time to calculate the semitotal edge domination number of a tree.Next,we prove that in a planar bipartite graph with maximum degree 4 to decide whether edge domination number is equal to semitotal edge domination number and whether seimtotal edge domination number is equal to total edge domination number are NP-hard.Last,we character trees satisfying the edge domination number is equal to semitotal edge domination number and semitotal edge domination number is equal to total edge domination number,respectively.In Chapter 4,the total edge domination number may change after adding any new edge.We mainly study some properties of this kind of graph whose total edge domination number remains unchanged after adding any edge,we also character the graphs with total edge domination 2 and the total edge domination number remains unchanged after adding any edge.