Nondeficient sets in graphs - Arumugam S.; Kumar, R. Anantha; Rao S.B. (Utilitas Mathematica, 2018)
Let G = (VtE) be a graph without isolated vertices. A subset U C V is called a nondeficient set in G if (S) >| S for all S C U. The maximum cardinality of a nondeficient set of G is called the nondeficient number of G and is denoted by nd(G). Any nondeficient set U with = nd(G) is called a not-set of G. In this paper we initiate a study of this parameter and determine the nondeficient number of several families of graphs. We characterize graphs G for which V(G) is a nd-set. Also we determine the value nd(G) in terms of critical independence number of G. Further we obtain lower and upper bounds for ndG) and characterize graphs which attain the upper bound. © 2018 Utilitas Mathematica Publishing Incorporated. All rights reserved.