- Title
- Nondeficient sets in graphs
- Creator
- Arumugam, S; Kumar, RA; Rao, SB
- Relation
- Utilitas Mathematica Vol. 109, p. 181-195
- Publisher
- University of Manitoba, Department of Computer Science
- Resource Type
- journal article
- Date
- 2018
- Description
- Let G = (V, E) be a graph without isolated vertices. A subset U ⊆ V is called a nondeficient set in G if ∣ N(S)∣ ≥ S ∣ for all S ⊆ 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 nd-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 and-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.
- Identifier
- http://hdl.handle.net/1959.13/1409802
- Identifier
- uon:36061
- Identifier
- ISSN:0315-3681
- Language
- eng
- Reviewed
- Hits: 2130
- Visitors: 1071
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|