Complexity and characterization aspects of edge-related domination for graphs
- PDF / 935,186 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 35 Downloads / 177 Views
Complexity and characterization aspects of edge-related domination for graphs Zhuo Pan1 · Xianyue Li1 · Shou-Jun Xu1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract For a connected graph G = (V , E), a subset F of E is 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 study a parameter, called the semitotal edge domination number, which is squeezed between γ (G) and γt (G). A semitotal edge dominating set is an edge dominating set S such that, for every edge e in S, there exists such an edge e in S that e either is adjacent to e or shares a common neighbor edge with e . The semitotal edge domination number, denoted by γst (G), is the minimum cardinality of a semitotal edge dominating set of G. In this paper, we prove that the problem of deciding whether γ (G) = γst (G) or γt (G) = γ (G) is NP-hard even when restricted to planar graphs with maximum degree 4. We also characterize trees with equal edge domination and semitotal edge domination numbers (Pan et al. in The complexity of total edge domination and some related results on trees, J Comb Optim, 2020, https://doi.org/10.1007/s10878-02000596-y, we characterized trees with equal edge domination and total edge domination numbers). Keywords Semitotal edge domination · Edge domination · Total edge domination · Trees · NP-hardness
1 Introduction The edge dominating problems have been extensively studied in graphs and have many applications in resource allocation, network routing, and encoding theory problems
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
(Haynes et al. 1998a, b; Arumugam and Velammal 1998; Srinivasan et al. 1995; Horton and Kilakos 1993; Mitchell and Hedetniemi 1977; Kilakos 1998; Xu 2006; Yannakakis and Gavril 1980; Kulli and Patwari 1991). In this paper, we mainly focus on semitotal edge domination which is a variant of edge domination, also an enhancement of edge domination and a relaxation of total edge domination. Let G be a finite simple undirected graph with edge set E. An edge dominating set (ED-set for short), proposed by Mitchell and Hedetniemi (1977), of G is a subset F of E such that any edge that is not in F is adjacent to one edge in F. The edge domination number of G, 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. A total edge dominating set (TED-set for short), introduced by Kulli and Patwari (1991), is an edge dominating set F with the property that F contains no isolated edge. The total edge domination number of G,
Data Loading...
