Extremal subgraphs with respect to vertex degree bounds
type: Item
instance of: scholarly article
title: Extremal subgraphs with respect to vertex degree bounds
zbMATH Open document ID: 1028.05047
DOI: 10.1016/S0012-365X(02)00772-0
author: Dieter Rautenbach
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 2003-04-09T00:00:00Z
review text: A weighted graph \(G= (V,E)\) with integer weights \(w(v)\) on its vertices is considered. The authors study the maximal (minimal) number of edges in a spanning subgraph \(H\) of \(G\) with \(d(v,H)\leq w(v)\) \((d(v,H)\geq w(v))\) for all \(v\in V\). These notions generalise the concepts of maximum matching and minimum edge cover for graphs. The obtained results include the well-known theorems of König and Gallai concerning the maximum matching and minimum vertex or edge cover.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1896009
zbMATH Keywords: weighted graph
zbMATH Keywords: vertex cover
zbMATH Keywords: edge cover
zbMATH Keywords: independent set
zbMATH Keywords: matching
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1896009