Extremal subgraphs with respect to vertex degree bounds (Q1869226)

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.