The complexity of total edge domination and some related results on trees
- PDF / 824,588 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 19 Downloads / 176 Views
The complexity of total edge domination and some related results on trees Zhuo Pan1 · Yu Yang1 · Xianyue Li1
· Shou-Jun Xu1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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\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 edge domination number (resp. total edge domination number) of G, denoted by γ (G) (resp. γt (G)). In the present paper, we first prove that the total edge domination problem is NP-complete for bipartite graphs with maximum degree 3. Then, for a graph G, we give the inequality γ (G) ≤ γt (G) ≤ 2γ (G) and characterize the trees T which obtain the upper or lower bounds in the inequality. Keywords Edge domination · Total edge domination · NP-completeness · Trees
1 Introduction Dominating problems have been subject of many studies in graph theory, and have many applications in operations research, e.g., in resource allocation and network routing, as well as in coding theory (Cockayne and Hedetniemi 1977; Kalbflisch et al. 1971). This paper mainly focuses on the total edge domination which is one of many variants of domination. Edge domination, a variant of domination, is introduced by Mitchell and Hedetniemi (1977) and is related to telephone switching network (Lru 1968). Edge domination is also related to the approximation of the vertex cover problem, since an independent edge dominating set is a matching (Karp 1972).
Zhuo Pan and Yu Yang have contributed equally to this paper.
B 1
Shou-Jun Xu [email protected] School of Mathematics and Statistics, Gansu Key Laboratory of Applied Mathematics and Complex Systems, Lanzhou University, Lanzhou 730000, Gansu, China
123
Journal of Combinatorial Optimization
In this paper, we, in general, follow Haynes et al. (1998) for notation and graph theory terminology. All graphs considered here are finite, undirected, connected, and have no loops or multiple edges. Let G = (V , E) be a graph with vertex set V and edge set E. A subset F of E is called an edge dominating set (abbreviated as ED-set) of G if every edge not in F is adjacent to at least one edge in F. The edge domination number, denoted by γ (G), is the minimum cardinality of an ED-set of G. An ED-set of G with cardinality γ (G) is called a γ (G)-set. The edge domination problem has been studied by several authors Horton and Kilakos (1993), Kilakos (1998), Xu (2006), Yannakakis and Gavril (1980). Yannakakis and Gavril (1980) showed that the edge domination problem is NP-complete even for planar or bipartite graphs of maximum degree 3, but solvable for trees and claw-free chordal graphs. The concept of the total edge domination, a variant of edge domination, was introduced by Kulli and Patwari (1991). A subset Ft of E is called a total edge dominating set (abbreviated as TED-set) of G if every e
Data Loading...
