Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911485398089728 |
|---|---|
| author | Grippo, Luciano N. Lin, Min Chih Vera, Camilo |
| author_facet | Grippo, Luciano N. Lin, Min Chih Vera, Camilo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04598 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets Grippo, Luciano N. Lin, Min Chih Vera, Camilo Combinatorics 05C70, 05C85, 05A99 68R10, 68Q25 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. |
| title | Perfect Edge Domination in $P_6$-free Graphs and in Graphs Without Efficient Edge Dominating Sets |
| topic | Combinatorics 05C70, 05C85, 05A99 68R10, 68Q25 |
| url | https://arxiv.org/abs/2509.04598 |