Extendability and factor-criticality
type: Item
instance of: scholarly article
title: Extendability and factor-criticality
zbMATH Open document ID: 0943.05066
DOI: 10.1016/S0012-365X(99)00172-7
published in: Discrete Mathematics
publication date: 2000-08-28T00:00:00Z
review text: A graph \(G\) is is said to be \(p\)-factor-critical if \(G-S\) has a perfect matching for each \(S\subset V(G)\) with \(|S|=p\). A graph \(G\) is \(p\)-extendable if any set of \(p\) independent edges is contained in a perfect matching. The author shows that for even \(p\) every non-bipartite \(p\)-extendable graph of even order is \(p\)-factor-critical, and every non-bipartite \((p+1)\)-extendable graph of even order is such that \(G-e\) is \(p\)-factor-critical for every edge \(e\in E(G)\). This generalizes results of \textit{M. D. Plummer} [On \(n\)-extendable graphs, Discrete Math. 31, No. 2, 201-210 (1980; Zbl 0442.05060)] on bicritical graphs.
reviewed by: Fedor V. Fomin
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1420379
zbMATH Keywords: factor-critical graph
zbMATH Keywords: extendable graph
zbMATH Keywords: perfect matching
zbMATH Keywords: independence number
author: Odile Favaron
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1420379