The Algorithm About The Total Edge Domination Problem In Cactus Graphs And Block Graphs

Let G=(V,E)be a graph with the vertex set V and the edge set E.A subset D C E is,called a total edge domination set if every edge e ? E is adjacent to at least one edge in D.The total edge domination problem is to find a minimum total edge domination set of G.The minimum number of total edge domination set of a graph G is called the total edge domination number,which is denoted as ?'t(G).For a graph G,a vertex v is a cut vertex if the number of connected components is increases after removing v,a block of a graph is a maximal connected subgraph which without cut vertices.A graph G is called a cactus graph if every block of G is either a cycle or an edge,and the intersection of two blocks is either empty or a cut vertex.Similarly,a graph is called a block graph if every block of G is either a clique or an edge.This paper studies the total edge domination problem in graph from an algorithmic point of view.In order to study the problem of total edge domination problem on cactus graphs and block graphs,the algorithm of tree is given by labeling method at first,and then the linear time algorithm of cactus graphs is given.Although the block graph is similar to cactus graph,the solution is quite different.So the linear time algorithm of total domination problem on block graphs is also given in this paper.