EUVIMEDEUVIMED entdecken
Crossref

Perfect edge domination in P6-free graphs and in graphs without efficient edge dominating sets

Luciano N. Grippo, Min Chih Lin, Camilo Vera

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →