Efficient recognition of equimatchable graphs

DOI10.1016/J.IPL.2013.08.002zbMATH Open1329.05243OpenAlexW1985402434MaRDI QIDQ2350604FDOQ2350604

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

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

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)

Cites Work

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

Cited In (14)

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

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)