×

Node-weighted graphs having the König-Egerváry property. (English) Zbl 0558.05054

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

MSC:

05C75 Structural characterization of families of graphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI