Efficient recognition of equimatchable graphs

DOI10.1016/J.IPL.2013.08.002MaRDI QIDQ2350604zbMATH OpenOpenAlexFDO

Authors 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 algorithmsedge dominating setmaximal matchingequimatchable

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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)

Recommendations

• scientific article; zbMATH DE number 3873377
• Equimatchable claw-free graphs
• On three extensions of equimatchable graphs
• Edge-stable equimatchable graphs
• On two extensions of equimatchable graphs

Cites work

• scientific article; zbMATH DE number 3873377 (Why is no real title available?)
• scientific article; zbMATH DE number 5717196 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs
• Bounding the size of equimatchable graphs of fixed genus
• Equimatchable factor‐critical graphs
• Matching theory
• Matching-perfect and cover-perfect graphs
• On two equimatchable graph classes
• Paths, Trees, and Flowers
• Randomly matchable graphs
• The structure of well-covered graphs and the complexity of their recognition problems

Cited in

(14)

• A classification of 1-well-covered graphs
• On two extensions of equimatchable graphs
• An efficient algorithm to recognize locally equivalent graphs
• scientific article; zbMATH DE number 2170450 (Why is no real title available?)
• Triangle‐free equimatchable graphs
• Equimatchable graphs are \(C_{2k+1}\)-free for \(k\geq 4\)
• Equimatchable claw-free graphs
• Equimatchable bipartite graphs
• Weighted well-covered claw-free graphs
• Efficiently recognizing graphs with equal independence and annihilation numbers
• 1-well-covered graphs containing a clique of size \(n/3\)
• scientific article; zbMATH DE number 7145105 (Why is no real title available?)
• Edge-stable equimatchable graphs
• Well-indumatched Trees and Graphs of Bounded Girth

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

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