On strong (weak) independent sets and vertex coverings of a graph

A vertex v in a graph G = (V, E) is strong, (weak) if deg(v) >= deg(u) (deg(v) <= deg(u)) for every u adjacent to v in G. A set S C V is said to be strong (weak) if every vertex in S is a strong (weak) vertex in G. A strong (weak) set which is independent is called a strong independent set [SIS] (weak independent set [WIS]). The strong (weak) independence number s alpha = s alpha(G) (w alpha = w alpha(G)) is the maximum cardinality of an SIS (WIS). For an edge x = uv, v strongly covers the edge x if deg(v) >= deg(u) in G. Then u weakly covers x. A set S C V is a strong vertex cover [SVC] (weak vertex cover [WVC]) if every edge in G is strongly (weakly) covered by some vertex in S. The strong (weak) vertex covering number s beta = s beta(G) (w beta = w beta(G)) is the minimum cardinality of an SVC (WVC). In this paper, we investigate some relationships among these four new parameters. For any graph G without isolated vertices, we show that the following inequality chains hold: s alpha <= beta <= s beta <= w beta and s alpha <= w alpha < alpha <= w beta. Analogous to Gallai's theorem, we prove s beta + w alpha = p and w beta + s alpha = p. Further, we show that s alpha <= p -Delta and w alpha <= p - delta and find a necessary and sufficient condition to attain the upper bound, characterizing the graphs, which attain these bounds. Several Nordhaus-Gaddum-type results and a Vizing-type result are also established. (c) 2006 Published by Elsevier B.V.