Hertz, Alain, Lozin, Vadim, Ries, Bernard, Zamaraev, Viktor 
ORCID: 0000-0001-5755-4141 and de Werra, Dominique
(2018)
Dominating induced matchings in graphs containing no long claw.
JOURNAL OF GRAPH THEORY, 88 (1).
pp. 18-39.
|
Text
1505.02558v1.pdf - Submitted version Download (4MB) | Preview |
Abstract
An induced matching $M$ in a graph $G$ is dominating if every edge not in $M$ shares exactly one vertex with an edge in $M$. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph $G$ contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw-free graphs. In the present paper, we study this problem for graphs containing no long claw, i.e. no induced subgraph obtained from the claw by subdividing each of its edges exactly once. To solve the problem in this class, we reduce it to the following question: given a graph $G$ and a subset of its vertices, does $G$ contain a matching saturating all vertices of the subset? We show that this question can be answered in polynomial time, thus providing a polynomial-time algorithm to solve the dominating induced matching problem for graphs containing no long claw.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | dominating induced matching, graphs containing no long claw, polynomial-time algorithm |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 07 Sep 2020 08:03 |
| Last Modified: | 18 Jan 2023 23:35 |
| DOI: | 10.1002/jgt.22182 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3100226 |
Dimensions
Dimensions
