Neighborhood unions and factor critical graphs
type: Item
instance of: scholarly article
title: Neighborhood unions and factor critical graphs
zbMATH Open document ID: 0934.05102
DOI: 10.1016/S0012-365X(99)00104-1
author: Hikoe Enomoto
author: Michael D. Plummer
author: Akira Saito
published in: Discrete Mathematics
publication date: 2000-04-09T00:00:00Z
review text: A graph \(G\) is \(n\)-factor-critical if \(G - S\) has a perfect matching for any set \(S\) of \(n\) vertices of \(G\). A sufficient condition in terms of generalized degrees of independent sets is given that implies a graph is \(n\)-factor-critical. More specifically, it is shown that if \(G\) is a \(k\)-connected graph of order \(p\), \(n\) is an integer with \(0 \leq n \leq k\) and \(p \equiv n\) (mod \(2\)), \(\alpha\) is a real number with \(1/2 \leq \alpha \leq 1\), and \(|N_G(A)|> \alpha(p - 2k + n - 2) + k\) for every independent set \(A\) of \(G\) with \(|A|= \lfloor \alpha(k - n + 2) \rfloor\), then \(G\) is \(n\)-factor-critical.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1334689
zbMATH Keywords: neighborhood union
zbMATH Keywords: \(n\)-factor critical
zbMATH Keywords: \(n\)-extendable
zbMATH Keywords: perfect matching
zbMATH Keywords: independent set
reviewed by: Ralph Faudree
MaRDI profile type: Publication
cites work: Q3818315
cites work: Neighbourhood unions and Hamiltonian properties in graphs
cites work: On \(k\)-factor-critical graphs
cites work: Q3972523
full work available at URL: s0012-365x(99)00104-1
OpenAlex ID: W2135972039
description: scientific article; zbMATH DE number 1334689