Toughness and matching extension in graphs
type: Item
instance of: scholarly article
title: Toughness and matching extension in graphs
zbMATH Open document ID: 0683.05034
DOI: 10.1016/0012-365X(88)90221-X
author: Michael D. Plummer
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: The author gives two results connecting the toughness of a graph with its matching extendability. Let G be a graph with a perfect matching, G is said to be n-extendable if every matching of size n in G extends to a perfect matching. The toughness of G, denoted tough(G), is the minimum over all vertex cutsets S of the quantity \(| S| /c(G-s)\) where c(G-S) is the number of components of G-S. The author proves the following results: 1. If \(tough(G)>n\), a positive integer, then G is n- extendable. 2. If G has p vertices, G is n-extendable, and \(tough(G)<1\) then \(n\leq (p-2)/6\).
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4118406
zbMATH Keywords: matching extendability
zbMATH Keywords: toughness
MaRDI profile type: Publication
cites work: Q5422499
cites work: Tough graphs and Hamiltonian circuits.
cites work: Q3215240
cites work: Paths, Trees, and Flowers
cites work: Brick decompositions and the matching rank of graphs
cites work: Toughness and the existence ofk-factors
cites work: Q5520564
cites work: Q5508779
cites work: Q3267903
cites work: Q5329577
cites work: On the structure of factorizable graphs
cites work: Matching theory
cites work: On n-extendable graphs
cites work: Q4732491
cites work: Q3800093
cites work: Q5202207
cites work: Matching extension and the genus of a graph
description: scientific article; zbMATH DE number 4118406