Abstract
A graphG having a 1-factor is calledn-extendible if every matching of sizen extends to a 1-factor. LetG be a 2-connected graph of order 2p. Letr≥0 andn>0 be integers such thatp−r≥n+1. It is shown that ifG/S isn-extendible for every connected subgraphS of order 2r for whichG/S is connected, thenG isn-extendible.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chartrand, G., Lesniak, L.: Graphs & Digraphs, 2nd ed., Wadsworth 1986
Enomoto, H.: Private Communication
Nishimura, T.: A theorem onn-extendable graphs. Ars Comb.38, 3–5 (1994)
Nishimura, T.: Extendable graphs and induced subgraphs. SUT Journal of Mathematics30, 129–135 (1994)
Nishimura, T., Saito, A.: Two recursive theorems onn-extendibility. Preprint
Plummer, M.D.: Onn-extendable graphs. Discrete Math.31, 201–210 (1980)
Summer, D.P.: Graphs with 1-factors. Proc. Amer. Math. Soc.42, 8–12 (1974)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nishimura, T. A new recursive theorem onn-extendibility. Graphs and Combinatorics 13, 79–83 (1997). https://doi.org/10.1007/BF01202239
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01202239