Graphs in which some and every maximum matching is uniquely restricted

DOI10.1002/JGT.22239MaRDI QIDQ4553727zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Uéverton dos Santos Souza, Lucia Draque Penso

Publication date 31 October 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.02250

zbMATH Keywords

maximum matchinguniquely restricted matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A matching $M$ in a graph $G$ is uniquely restricted if there is no matching $M^{\prime }$ in $G$ that is distinct from $M$ but covers the same vertices as $M$. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.

Recommendations

• On unicyclic graphs with uniquely restricted maximum matchings
• Unicycle graphs and uniquely restricted maximum matchings
• On the maximum uniquely restricted matching for bipartite graphs
• On some graphs with a unique perfect matching
• On graphs with a unique perfect matching
• Uniquely restricted matchings in interval graphs
• The matching uniqueness of a graphs
• scientific article; zbMATH DE number 1665451
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• Uniquely restricted matchings in subcubic graphs

Cited in

(19)

• Graphs with restricted valency and matching number
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Lower bounds on the uniquely restricted matching number
• Generalized subgraph-restricted matchings in graphs
• Perfect matching cuts partitioning a graph into complementary subgraphs
• On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• Approximating maximum uniquely restricted matchings in bipartite graphs
• On the hardness of deciding the equality of the induced and the uniquely restricted matching number
• Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
• On unicyclic graphs with uniquely restricted maximum matchings
• scientific article; zbMATH DE number 1665451 (Why is no real title available?)
• Uniquely restricted matchings in interval graphs
• Unicycle graphs and uniquely restricted maximum matchings
• scientific article; zbMATH DE number 6129705 (Why is no real title available?)
• Upper bounds on the uniquely restricted chromatic index
• Uniquely restricted matchings
• Uniquely restricted matching extendable graphs
• Perfect matching cuts partitioning a graph into complementary subgraphs

This page was built for publication: Graphs in which some and every maximum matching is uniquely restricted

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