Nigmatullin, R. G.; Shtivel’man, V. K. Single and multiple coverings of graphs by edges. (Russian) Zbl 0658.05061 Veroyatn. Metody Kibern. 21, 86-94 (1985). 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.) Keywords:integral k-cover; fractional k-cover; sum of edge-weights; bipartite; shortest odd cycle PDFBibTeX XMLCite \textit{R. G. Nigmatullin} and \textit{V. K. Shtivel'man}, Veroyatn. Metody Kibern. 21, 86--94 (1985; Zbl 0658.05061) Full Text: EuDML