Dominating induced matchings in graphs containing no long claw

DOI10.1002/JGT.22182MaRDI QIDQ4575515zbMATH OpenOpenAlexFDO

Authors Alain Hertz, Bernard Ries, Victor Zamaraev, Dominique De Werra, Vadim Lozin

Publication date 13 July 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.02558, http://wrap.warwick.ac.uk/92509/7/WRAP-dominating-induced-matchings-Lozin-2017.pdf

zbMATH Keywords

dominating induced matchinggraphs containing no long clawpolynomial-time algorithm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
• Dominating induced matchings in graphs without a skew star
• Dominating induced matchings
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time

Cited in

(18)

• Perfect edge domination: hard and solvable cases
• On the dominating induced matching problem: spectral results and sharp bounds
• Independent feedback vertex set for P₅-free graphs
• Some results on dominating induced matchings
• Finding dominating induced matchings in P₉-free graphs in polynomial time
• Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs
• Modelling and solving the perfect edge domination problem
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Dominating induced matchings in graphs without a skew star
• A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
• Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
• Dominating induced matching in some subclasses of bipartite graphs
• Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time
• Graphs whose vertices of degree at least 2 lie in a triangle
• Dominating induced matchings and other graph parameters
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Perfect edge domination in P₆-free graphs and in graphs without efficient edge dominating sets
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time

This page was built for publication: Dominating induced matchings in graphs containing no long claw

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575515)