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

A vertex vv in a graph G=(V,E)G=(V,E) is strong (weak  ) if deg(v)⩾deg(u)deg(v)⩾deg(u)(deg(v)⩽deg(u))(deg(v)⩽deg(u)) for every u   adjacent to vv in G  . A set S⊆VS⊆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α=sα(G)(wα=wα(G))sα=sα(G)(wα=wα(G)) is the maximum cardinality of an SIS (WIS). For an edge x=uvx=uv, vvstrongly covers the edge x   if deg(v)⩾deg(u)deg(v)⩾deg(u) in G. Then u weakly covers x  . A set S⊆VS⊆V is a strong vertex cover [SVC] (weak vertex cover [WVC]) if every edge in G   is strongly (weakly) covered by some vertex in SS. The strong (weak) vertex covering number  sβ=sβ(G)sβ=sβ(G)(wβ=wβ(G))(wβ=wβ(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α⩽β⩽sβ⩽wβsα⩽β⩽sβ⩽wβ and sα⩽wα⩽α⩽wβsα⩽wα⩽α⩽wβ. Analogous to Gallai's theorem, we prove sβ+wα=psβ+wα=p and wβ+sα=pwβ+sα=p. Further, we show that sα⩽p-Δsα⩽p-Δ and wα⩽p-δwα⩽p-δ 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.