×

Single and multiple coverings of graphs by edges. (Russian) Zbl 0658.05061

For a natural number k, an integral k-cover [fractional k-cover] of a graph G is an assignment of nonnegative integral [rational] weights \(w_ e\) to edges of G such that \(\sum_{N(v)}w_ e\geq k\) at every vertex v(N(v) is the set of edges incident with v). Let \(w^ F_ k[w^ I_ k]\) be the minimum possible value of the sum of edge-weights in G among all fractional [integral] k-covers of G. Clearly, \(w^ F_ k\leq \omega^ K_ k\leq k\cdot w^ I_ 1.\) In the paper, the author proves \(k\cdot w^ I_ 1\leq ((p+1)/p)\cdot w^ F_ k,\) where \(p=3\) for bipartite G, otherwise p is the length of the shortest odd cycle in G. This bound is sharp.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: EuDML