Computing unique maximum matchings in O(m) time for König-Egerváry graphs and unicyclic graphs
From MaRDI portal
Publication:328720
DOI10.1007/S10878-015-9875-9zbMATH Open1354.90155arXiv1402.2903OpenAlexW2027498052MaRDI QIDQ328720FDOQ328720
Eugen Mandrescu, Vadim E. Levit
Publication date: 20 October 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Abstract: Let alpha(G) denote the maximum size of an independent set of vertices and mu(G) be the cardinality of a maximum matching in a graph G. A matching saturating all the vertices is perfect. If alpha(G) + mu(G) equals the number of vertices of G, then it is called a Konig-Egervary graph. A graph is unicyclic if it has a unique cycle. In 2010, Bartha conjectured that a unique perfect matching, if it exists, can be found in O(m) time, where m is the number of edges. In this paper we validate this conjecture for Konig-Egervary graphs and unicylic graphs. We propose a variation of Karp-Sipser leaf-removal algorithm (Karp and Spiser, 1981), which ends with an empty graph if and only if the original graph is a Konig-Egervary graph with a unique perfect matching obtained as an output as well. We also show that a unicyclic non-bipartite graph G may have at most one perfect matching, and this is the case where G is a Konig-Egervary graph.
Full work available at URL: https://arxiv.org/abs/1402.2903
Recommendations
Cites Work
- Ear-decompositions of matching-covered graphs
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Title not available (Why is that?)
- Ranks of zero patterns and sign patterns*
- On the spectral radius of unicyclic graphs with prescribed degree sequence
- Deciding the deterministic property for soliton graphs
- The uniquely solvable bipartite matching problem
- The spread of the unicyclic graphs
- The dependence graph for bases in matroids
- Combinatorial properties of the family of maximum stable sets of a graph
- Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
- Very well covered graphs
- On \(\alpha^{+}\)-stable König-Egerváry graphs
- Critical independent sets and König-Egerváry graphs
- On maximum matchings in König-Egerváry graphs
- Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
- Unique maximum matching algorithms
- VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS
- Deterministic soliton graphs
- Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
- Local maximum stable set greedoids stemming from very well-covered graphs
- On the core of a unicyclic graph
- Title not available (Why is that?)
- Uniquely restricted matchings
- On the structure of \(\alpha\)-stable graphs
- A characterization of the graphs in which the transversal number equals the matching number
- The smallest values of algebraic connectivity for unicyclic graphs
- The critical independence number and an independence decomposition
- On the intersection of all critical sets of a unicyclic graph
- Minimizing the least eigenvalue of unicyclic graphs with fixed diameter
Cited In (5)
This page was built for publication: Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q328720)
