Dominating induced matchings in graphs containing no long claw
- Hertz, Alain Department of Mathematics and Industrial Engineering
- Lozin, Vadim Mathematics Institute
- Ries, Bernard Department of Informatics
- Zamaraev, Viktor Mathematics Institute
- de Werra, Dominique Institute of Mathematics
-
2017
Published in:
- Journal of Graph Theory. - 2017, vol. 88, no. 1, p. 18-39
English
An induced matching 𝑀 in a graph 𝐺 is dominating if every edge not in 𝑀 shares exactly one vertex with an edge in 𝑀. The DOMINATING INDUCED MATCHING problem (also known as EFFICIENT EDGE DOMINATION) asks whether a graph 𝐺 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 algorithmto 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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Economics
- License
- License undefined
- Identifiers
-
- RERO DOC 324392
- DOI 10.1002/jgt.22182
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307795
Statistics
Document views: 38
File downloads:
- jgt_rero.pdf: 76