A Study on the Nourishing Number of Graphs and Graph Powers

Abstract

Let \(\mathbb{N}_{0}\) be the set of all non-negative integers and \(\mathcal{P}(\mathbb{N}_{0})\) be its power set. Then, an integer additive set-indexer (IASI) of a given graph \(G\) is defined as an injective function \(f:V(G)\to \mathcal{P}(\mathbb{N}_{0})\) such that the induced edge-function \(f^+:E(G) \to\mathcal{P}(\mathbb{N}_{0})\) defined by \(f^+ (uv) = f(u)+ f(v)\) is also injective, where \(f(u)+f(v)\) is the sumset of \(f(u)\) and \(f(v)\). An IASI \(f\) of \(G\) is said to be a strong IASI of \(G\) if \(|f^+(uv)|=|f(u)|\,|f(v)|\) for all \(uv\in E(G)\). The nourishing number of a graph \(G\) is the minimum order of the maximal complete subgraph of \(G\) so that \(G\) admits a strong IASI. In this paper, we study the characteristics of certain graph classes and graph powers that admit strong integer additive set-indexers and determine their corresponding nourishing numbers.

Keywords

• graph powers
• integer additive set-indexers
• strong integer additive set-indexers
• nourishing number of a graph