Efficient recognition of equimatchable graphs

DOI10.1016/j.ipl.2013.08.002zbMath1329.05243OpenAlexW1985402434MaRDI QIDQ2350604

Marc Demange, Tınaz Ekim

Publication date: 25 June 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.08.002

zbMATH Keywords

graph algorithmsmaximal matchingedge dominating setequimatchable

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 (9)

Equimatchable claw-free graphs ⋮ Edge-stable equimatchable graphs ⋮ A classification of 1-well-covered graphs ⋮ Triangle‐free equimatchable graphs ⋮ Well-indumatched Trees and Graphs of Bounded Girth ⋮ Weighted well-covered claw-free graphs ⋮ On two extensions of equimatchable graphs ⋮ Equimatchable graphs are \(C_{2k+1}\)-free for \(k\geq 4\) ⋮ Equimatchable bipartite graphs

Cites Work

• Bounding the size of equimatchable graphs of fixed genus
• Matching theory
• Matching-perfect and cover-perfect graphs
• The structure of well-covered graphs and the complexity of their recognition problems
• A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs
• On two equimatchable graph classes
• Randomly matchable graphs
• Equimatchable factor‐critical graphs
• Paths, Trees, and Flowers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient recognition of equimatchable graphs