Perfect edge domination in P6-free graphs and in graphs without efficient edge dominating sets
Theoretical Computer Science · 2026-09 · 1082 · 116142
DOI: 10.1016/j.tcs.2026.116142 ↗Kurz gefasst
Fachartikel in der Zeitschrift Theoretical Computer Science, 2026-09. Verfasst von Luciano N. Grippo und 2 weiteren Autor:innen. Die Arbeit nennt 26 Literaturangaben.
Abstract (Originalsprache)
An edge of a graph dominates itself along with any edge that shares an endpoint with it. An efficient edge dominating set (also called a dominating induced matching, DIM) is a subset of edges such that each edge of the graph is dominated by exactly one edge in the subset. A perfect edge dominating set is a subset of edges in which every edge outside the subset is dominated by exactly one edge within it. In this article, we establish the NP-completeness of deciding whether a graph that does not admit any efficient edge dominating set has at least two perfect edge dominating sets. We also present a cubic time algorithm designed to identify a perfect dominating set of minimal cardinality for $P_6$-free graphs. Moreover, we show how this algorithm can be adapted to handle the weighted version of the problem and to count all perfect edge dominating sets as well as DIMs in a given graph, while preserving the same time complexity.
Zitieren
APA
Grippo, L. N., Lin, M. C., & Vera, C. (2026). Perfect edge domination in P6-free graphs and in graphs without efficient edge dominating sets. Theoretical Computer Science, 1082, 116142. https://doi.org/10.1016/j.tcs.2026.116142
Vancouver
Grippo LN, Lin MC, Vera C. Perfect edge domination in P6-free graphs and in graphs without efficient edge dominating sets. Theoretical Computer Science. 2026;1082:116142. doi:10.1016/j.tcs.2026.116142
BibTeX
@article{Grippo2026,
author = {Grippo, Luciano N. and Lin, Min Chih and Vera, Camilo},
title = {Perfect edge domination in P6-free graphs and in graphs without efficient edge dominating sets},
journal = {Theoretical Computer Science},
year = {2026},
volume = {1082},
pages = {116142},
doi = {10.1016/j.tcs.2026.116142}
}
EUVIMED