Dominating induced matchings in graphs containing no long claw

DOI10.1002/jgt.22182zbMath1391.05207arXiv1505.02558OpenAlexW2963516633MaRDI QIDQ4575515

Victor Zamaraev, Dominique de Werra, Alain Hertz, Bernard Ries, Vadim V. 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

zbMATH Keywords

polynomial-time algorithmdominating induced matchinggraphs containing no long claw

Mathematics Subject Classification ID

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

Related Items

Perfect edge domination: hard and solvable cases, Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time, Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs, Modelling and solving the perfect edge domination problem, On the dominating induced matching problem: spectral results and sharp bounds, Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time, Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time, Independent feedback vertex set for \(P_5\)-free 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 \(S_{1, 1, 5}\)-free graphs in polynomial time, Some results on dominating induced matchings