Bourjolly, J.-M.; Hammer, P. L.; Simeone, B. Node-weighted graphs having the König-Egerváry property. (English) Zbl 0558.05054 Math. Program. Study 22, 44-63 (1984). Let \(G=(V,E)\) be a finite, undirected, and connected graph without loops or multiple edges. Let \(b: V\to {\mathbb{N}}\) be a vertex-weight function. A b-matching is an edge-weight function \(\lambda\) : \(E\to {\mathbb{N}}_ 0\) where the sum of all edges incident with v does not exceed b(v) for all vertices \(v\in V\). A transversal is a set T V such that each edge \(e\in E\) has at least one endpoint in T. G is said to have the König- Egerváry property iff G has a b-matching \(\lambda\) and a transversal T satisfying \(\sum_{e\in E}\lambda (e)=\sum_{v\in T}b(v)\). Several characterizations and two polynomial algorithms for deciding this property are given. Reviewer: J.Ebert Cited in 1 ReviewCited in 15 Documents MSC: 05C75 Structural characterization of families of graphs 68R10 Graph theory (including graph drawing) in computer science Keywords:graph; b-matching; transversal; König-Egerváry property PDFBibTeX XMLCite \textit{J. M. Bourjolly} et al., Math. Program. Study 22, 44--63 (1984; Zbl 0558.05054) Full Text: DOI