We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Dominating induced matchings in graphs containing no long claw.
- Authors
Hertz, Alain; Lozin, Vadim; Ries, Bernard; Zamaraev, Viktor; de Werra, Dominique
- Abstract
Abstract: An induced matching <italic>M</italic> in a graph <italic>G</italic> is dominating if every edge not in <italic>M</italic> shares exactly one vertex with an edge in <italic>M</italic>. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph <italic>G</italic> 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 article, we provide a polynomial‐time algorithm to solve the dominating induced matching problem for graphs containing no long claw, that is, no induced subgraph obtained from the claw by subdividing each of its edges exactly once.
- Subjects
DOMINATING set; PATHS &; cycles in graph theory; POLYNOMIAL time algorithms; NP-complete problems; SUBGRAPHS
- Publication
Journal of Graph Theory, 2018, Vol 88, Issue 1, p18
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22182