Nondeficient sets in graphs

Abstract

Let G = (VtE) be a graph without isolated vertices. A subset U C V is called a nondeficient set in G if \N(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 \U\ = 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 nd{G) and characterize graphs which attain the upper bound. © 2018 Utilitas Mathematica Publishing Incorporated. All rights reserved.