Strong (Weak) Matchings & Edge Coverings Of A Graph
Radhakrishna Bhat, S. S. Kamath, Surekha R Bhat · 2012
Let G = (V, X) be a graph without isolates. Let de(x) denote the edge degree of an edge. An edge x=uv strongly (weakly) covers a vertex v if de(x)≥de(y) (de(x)≤ de(y)) for every edge y incident on v. A set L I X is a strong edge covering (SEC) [(weak edge covering (WEC)] if every vertex in G is strongly (weakly) covered by some edge in L. The strong edge covering number s1 = s1(G) (weak edge covering number w1 = w1(G)) is the cardinality of a minimum SEC (WEC) of G. An edge x is said to be strong (weak) if de (x)≥de(y)(de(x)≤de(y)) for every y adjacent to x. A set LX is a matching if no two edges in L are adjacent. A matching L of edges is a strong matching (SM) [weak matching (WM)] if every edge in L is strong (weak). The strong matching number sβ1 = sβ1(G) (Weak matching number wβ1 = wβ1(G)) is the cardinality of maximum SM (WM). In this paper, analogues to the Gallai’s theorem we prove that for any isolate free graph G with p vertices ss1+sβ1 = w1 + w1 = p. Further it is proved that the following inequality chain holds in any graph. sβ1≤wβ1<β1≤a1≤wa1≤sa1