Hertz, Alain, Lozin, Vadim V., Ries, Bernard, Zamaraev, Victor and de Werra, Dominique (2018) Dominating induced matchings in graphs containing no long claw. Journal of Graph Theory, 88 (1). pp. 18-39. doi:10.1002/jgt.22182 ISSN 0364-9024.

Preview

PDF WRAP-dominating-induced-matchings-Lozin-2017.pdf - Accepted Version - Requires a PDF viewer. Download (4Mb) | Preview

Request Changes to record.

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 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.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Graph theory
Journal or Publication Title:	Journal of Graph Theory
Publisher:	John Wiley & Sons Ltd.
ISSN:	0364-9024
Official Date:	May 2018
Dates:	Date Event May 2018 Published 6 September 2017 Available 20 August 2017 Accepted
Volume:	88
Number:	1
Page Range:	pp. 18-39
DOI:	10.1002/jgt.22182
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	22 September 2017
Date of first compliant Open Access:	6 September 2018
Funder:	Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	EP/L020408/1.

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads