Minimum order of a graph with given deficiency and either minimum or maximum degree
type: Item
instance of: scholarly article
zbMATH Open document ID: 0963.05108
publication date: 2001-06-10T00:00:00Z
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1602776
zbMATH Keywords: matching
zbMATH Keywords: deficiency
MaRDI profile type: Publication
author: Purwanto
author: Walter D. Wallis
title: Minimum order of a graph with given deficiency and either minimum or maximum degree
published in: Ars Combinatoria
review text: A matching of a graph \(G\) is a subset of its edge set such that no two edges of this set have a common end vertex. A matching of \(G\) with the maximum number of edges is called a maximum matching of \(G\). If \(M\) is a maximum matching of \(G\), then the number of vertices of \(G\) incident to no edge of \(M\) is called the deficiency def\((G)\) of \(G\). In the paper lower bounds for the number of vertices of a graph with given deficiency and given minimum degree and with given deficiency and given maximum degree are found.
reviewed by: Bohdan Zelinka
description: scientific article; zbMATH DE number 1602776