Paper Info
Title
Perfect edge domination and efficient edge domination in graphs
Abstract
Let G = (V,E) be a finite and undirected graph without loops and multiple edges. An edge is said to dominate itself and any edge adjacent to it. A subset D of E is called a perfect edge dominating set if every edge of E \ D is dominated by exactly one edge in D and an efficient edge dominating set if every edge of E is dominated by exactly one edge in D. The perfect (efficient) edge domination problem is to find a perfect (efficient) edge dominating set of minimum size in G. Suppose that each edge e is associated with a real number w(e) as its weight. Then, the weighted perfect (efficient) edge domination problem is to calculate a perfect (efficient) edge dominating set D such that the weight w(D) of D is minimum, where w(D)=Σe∈D w(e). In this paper, we show that the perfect (efficient) edge domination problem is NP-complete on bipartite (planar bipartite) graphs. Moreover, we present linear-time algorithms to solve the weighted perfect (efficient) edge domination problem on generalized series-parallel graphs and chordal graphs.
Year
DOI
Venue
2002
10.1016/S0166-218X(01)00198-6
Discrete Applied Mathematics
Keywords
Field
DocType
real number w,edge e,weight w,subset d,planar bipartite graphs,algorithms,edge domination problem,perfect edge,efficient edge domination,perfect edge domination,d w,minimum size,generalized series–parallel graphs,chordal graphs,efficient edge,multiple edge,chordal graph,bipartite graph,dominating set
Graph theory,Discrete mathematics,Dominating set,Combinatorics,Edge cover,Series-parallel graph,Bipartite graph,Edge dominating set,Chordal graph,Mathematics,Planar graph
Journal
Volume
Issue
ISSN
119
3
Discrete Applied Mathematics
Citations 
PageRank 
References 
18
1.16
15
Authors
3
Name
Order
Citations
PageRank
Chin Lung Lu142334.59
Ming-Tat Ko21320103.71
Chuan Yi Tang370479.25