Closure and factor-critical graphs
type: Item
instance of: scholarly article
title: Closure and factor-critical graphs
zbMATH Open document ID: 0951.05084
DOI: 10.1016/S0012-365X(99)00234-4
author: Michael D. Plummer
author: Akira Saito
published in: Discrete Mathematics
publication date: 2000-12-13T00:00:00Z
review text: A graph \(G\) is said to be \(n\)-factor-critical if \(G\setminus T\) has a perfect matching for each \(T\subset V(G)\) with \(|T|= n\). There is a close relationship between \(n\)-factor-criticality and matching extension. For every integer \(n\), \(0\leq n<|V(G)|/2\), a graph \(G\) is said to be \(n\)-extendable if \(G\) has a matching of size \(n\) and every matching of size \(n\) extends to a perfect matching of \(G\). \textit{O. Favaron} [Discuss. Math., Graph Theory 16, No. 1, 41-51 (1996; Zbl 0865.05061)] remarked that a \(2n\)-factor-critical graph is \(n\)-extendable. Here the authors study the relationship between \(n\)-factor-criticality and various closure operations which are usually considered in the theory of Hamiltonian graphs. For example, they show the following Bondy-Chvátal-type closure result. Theorem. Let \(G\) be a graph of order \(p\) and let \(x\) and \(y\) be a pair of distinct nonadjacent vertices of \(G\) with \(\deg_G x+\deg_G y\geq p+ n-1\). Then \(G\) is \(n\)-factor-critical if and only if \(G+ xy\) is \(n\)-factor-critical. The authors also investigate relationships between the various closures and matching extension.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1439832
zbMATH Keywords: factor-critical
zbMATH Keywords: perfect matching
zbMATH Keywords: matching extension
zbMATH Keywords: Hamiltonian graphs
reviewed by: Linda Lesniak
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00234-4
OpenAlex ID: W2024842496
Recommended article: On \(k\)-factor-critical graphs
Recommended article: Q4851767
Recommended article: Equivalence between Extendibility and Factor-Criticality
Recommended article: Equimatchable factor‐critical graphs
Recommended article: A characterization of maximal non-\(k\)-factor-critical graphs
Recommended article: Q4326749
Recommended article: Notes on factor-criticality, extendibility and independence number
Recommended article: Extendability and factor-criticality
Recommended article: Neighborhood unions and factor critical graphs
description: scientific article; zbMATH DE number 1439832