Abstract
A matching M of a graph G is called uniquely restricted if M is a unique perfect matching of the subgraph induced by M-saturated vertex set. A connected graph is called uniquely restricted matching extendable (abbreviated as \( URM \)-extendable) if every uniquely restricted matching is included in a perfect matching. A \( URM \)-extendable graph G is minimal if \(G-e\) is not \( URM \)-extendable for any edge e. In this paper, we find all \( URM \)-extendable cubic graphs. For any integer \(r\ge 1\), we construct some \((2r+1)\)-regular \( URM \)-extendable graphs and \((4r+2)\)-regular \( URM \)-extendable graphs. We show that \(T\otimes K_2\) is a minimal \( URM \)-extendable graph for any tree T. Finally, we show that the minimum size of \( URM \)-extendable graph G on 2n vertices is \(4n-4\) and characterize the extreme graph.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cameron, K.: Induced matchings. Discrete Appl. Math. 24, 97–102 (1989)
Golumbic, M.C., Hirst, T., Lewenstein, M.: Uniquely restricted matchings. Algorithmica 31(2), 139–154 (2001)
Hershkowitz, D., Schneider, H.: Ranks of zero patterns and sign patterns. Linear Multilinear A. 34, 3–19 (1993)
Plummer, M.D.: On \(n\)-extendable graphs. Discrete Math. 31, 201–210 (1980)
Yuan, J.: Induced matching extendable graph. J. Graph Theory 28, 203–213 (1998)
Gyori, E., Plummer, M.D.: The Cartesian product of a \(k\)-extendable and an l-extendable graph is \((k+l-1)\)-extendable. Discrete Math. 101, 87–96 (1992)
Plummer, M.D.: Extending matchings in graphs: a survey. Discrete Math. 127, 277–292 (1994)
Plummer, M.D.: Toughness and matching extension in graphs. Discrete Math. 72, 311–320 (1988)
Zhou, J., Yuan, J.: Characterization of induced matching extendable graphs with \(2n\) vertices and \(3n-1\) edges. Austr. J. Combin. 33, 255–263 (2005)
Zhou, J.: Characterization of the induced matching extendable graphs with \(2n\) vertices and \(3n\) edges. Discrete Math. 341(4), 1021–1031 (2018)
Acknowledgements
We would like to express our gratitude to two anonymous reviewers for their diligent review and valuable suggestions, which significantly enhanced the clarity and presentation of this paper. Special thanks to Dr. Xueli Su from Northwestern Polytechnical University for proofreading and providing valuable feedback on this article.
Funding
This work is supported by the Natural Science Foundation of Guangdong (No. 2021A1515012045), the National Natural Science Foundation of China (No. 12161073).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Chang, C., Liu, Y. Uniquely Restricted Matching Extendable Graphs. Graphs and Combinatorics 40, 68 (2024). https://doi.org/10.1007/s00373-024-02795-4
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-024-02795-4