Perfect edge domination: hard and solvable cases

Min Chih Lin (), Vadim Lozin (), Veronica A. Moyano () and Jayme L. Szwarcfiter ()
Additional contact information
Min Chih Lin: Consejo Nacional de Investigaciones Científicas y Técnicas
Vadim Lozin: University of Warwick
Veronica A. Moyano: Consejo Nacional de Investigaciones Científicas y Técnicas
Jayme L. Szwarcfiter: Universidade Federal do Rio de Janeiro

Annals of Operations Research, 2018, vol. 264, issue 1, No 11, 287-305

Abstract: Abstract Let G be an undirected graph. An edge of G dominates itself and all edges adjacent to it. A subset $$E'$$ E ′ of edges of G is an edge dominating set of G, if every edge of the graph is dominated by some edge of $$E'$$ E ′ . We say that $$E'$$ E ′ is a perfect edge dominating set of G, if every edge not in $$E'$$ E ′ is dominated by exactly one edge of $$E'$$ E ′ . The perfect edge dominating problem is to determine a least cardinality perfect edge dominating set of G. For this problem, we describe two NP-completeness proofs, for the classes of claw-free graphs of degree at most 3, and for bounded degree graphs, of maximum degree at most $$d \ge 3$$ d ≥ 3 and large girth. In contrast, we prove that the problem admits an O(n) time solution, for cubic claw-free graphs. In addition, we prove a complexity dichotomy theorem for the perfect edge domination problem, based on the results described in the paper. Finally, we describe a linear time algorithm for finding a minimum weight perfect edge dominating set of a $$P_5$$ P 5 -free graph. The algorithm is robust, in the sense that, given an arbitrary graph G, either it computes a minimum weight perfect edge dominating set of G, or it exhibits an induced subgraph of G, isomorphic to a $$P_5$$ P 5 .

Keywords: Claw-free graphs; Complexity dichotomy; Cubic graphs; NP-completeness; Perfect edge domination (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2664-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:264:y:2018:i:1:d:10.1007_s10479-017-2664-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2664-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().