Efficient coverage of edge sets in graphs
Abstract
Let G = (V, E) be a graph. The efficient covering number of G, denoted F01 (G), equals the maximum number of edges covered by a vertex set S with no edge in E(G) covered more than once. The redundance covering number R01 (G) equals the minimum total amount of coverage done by a cover. In this paper, we relate F01 (G) and R01 (G), compute F01 (G) where G = Pk x Ph, Pk x Ch and Ck x Ch, and bound F01 (G). We prove that if G is a graph of order n, then n - 1 ≤ F01 (G) + F01 (Ḡ) ≤ (n-1)(n+2)/3, characterize the graphs G of order n for which F01 (G) + F01 (Ḡ) = n - 1 and characterize the graphs G of order n for which F01(G) + F01(Ḡ) = (n-1)(n+2)/3. Also, we show that if G is a graph of order n, then 0 ≤ F01 (G)·F01(Ḡ) ≤ ((n-1)(n+2)/6)2, characterize the graphs G of order n for which F01 (G) · F01(Ḡ) = 0 and characterize the graphs G of order n for which F01(G) · F01(Ḡ) = ((n-1)(n+2)/6)2. Finally, we show that the decision problem corresponding to the computation of F01 (G) is NP-complete.
