2019/10/06 by Zhuo Pan, Yu Yang, Pan, Zhuo +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1910.02431
24 pages, 15 figures, 17 references
arxiv created 2019/10/13 · arxiv updated 2019/10/15
For a graph G = (V, E) with vertex set V and edge set E, a subset F of E is called an edge dominating set (resp. a total edge dominating set) if every edge in E\backslash F (resp. in E) is adjacent to at least one edge in F, the minimum cardinality of an edge dominating set (resp. a total edge dominating set) of G is the \em edge domination number (resp. \em total edge domination number) of G, denoted by γ'(G) (resp. γt'(G)). In the present paper, we prove that the total edge domination problem is NP-complete for bipartite graphs with maximum degree 3. We also design a linear-time algorithm for solving this problem for trees. Finally, for a graph G, we give the inequality γ'(G)\leqslant γ't(G)\leqslant 2γ'(G) and characterize the trees T which obtain the upper or lower bounds in the inequality.