<figure><img src="image_1.png" /></figure>

HAL
open science

# A Study on the Nourishing Number of Graphs and Graph Powers

Sudev Naduvath, Germina Augustine

<figure><img src="image_2.png" /></figure>

## To cite this version:

Sudev Naduvath, Germina Augustine. A Study on the Nourishing Number of Graphs and Graph Powers. Mathematics, 2015, 3 (1), pp.29-39. 10.3390/math3010029. hal-02263322

HAL Id: hal-02263322

https://hal.science/hal-02263322

Submitted on 4 Aug 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Article

# A Study on the Nourishing Number of Graphs and Graph Powers

**Sudev Naduvath**<sup>1,*</sup> and **Germina Augustine**<sup>2</sup>

Academic Editor: Indranil SenGupta

Received: 17 January 2015 / Accepted: 2 March 2015 / Published: 6 March 2015

**Abstract:** Let $N_0$ be the set of all non-negative integers and $P(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 P(N_0)$ such that the induced edge-function $f^+ : E(G) \to P(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

**MSC classifications:** 05C78

<footnote n="1">¹ Department of Mathematics, Vidya Academy of Science & Technology, Thalakkottukara, Thrissur 680501, Kerala, India</footnote>

<footnote n="2">² PG & Research Department of Mathematics, Mary Matha Arts & Science College, Mananthavady, Wayanad 670645, Kerala, India; E-Mail: srgerminaka@gmail.com</footnote>

<footnote>* Author to whom correspondence should be addressed; E-Mail: sudevnk@gmail.com; Tel.: +91-9497557876.</footnote>
# 1. Introduction

For all terms and definitions, not defined specifically in this paper, we refer to [1–4]. For more about different graph classes, we further refer to [5–7]. Unless mentioned otherwise, all graphs considered here are simple, finite and have no isolated vertices.

Let $\mathbb{N}_0$ denote the set of all non-negative integers. For all $A, B \subseteq \mathbb{N}_0$, define their sumset, denoted by $A + B$, as the set $A + B = \{a + b : a \in A, b \in B\}$. If either $A$ or $B$ is countably infinite, then their sumset is also countably infinite. Hence, the sets we consider here are all finite sets of non-negative integers. The cardinality of a set $A$ is denoted by $|A|$. The following theorem is on the minimum and maximum of the cardinality of the sumset of two non-empty sets of integers.

**Theorem 1.** [8] For any two non-empty sets $A$ and $B$ of integers, $|A| + |B| - 1 \le |A + B| \le |A||B|$.

Based on the concepts of sumsets of finite non-empty sets, an integer additive set-indexer of a given graph $G$ is defined as follows.

**Definition 1.** [9] An integer additive set-indexer (IASI, in short) of a given graph $G$ is 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. A graph which admits an IASI is called an integer additive set-indexed graph (strong IASI-graph).

The set-indexing number (see [10]) of an element (a vertex or an edge) of $G$ is the cardinality of the set-label of that element. The IASI $f$ of a given graph $G$ such that the set-indexing number of every edge of $G$ is the product of the set-indexing numbers of its end vertices is of special interest and hence we have defined the following.

**Definition 2.** [11] If a graph $G$ has a set-indexer $f : V(G) \to \mathcal{P}(\mathbb{N}_0)$ such that $|f^+(uv)| = |f(u)| + |f(v)|$ for all adjacent vertices $u$ and $v$ of $G$, then $f$ is said to be a strong IASI of $G$. A graph which admits a strong IASI is called a strong integer additive set-indexed graph (IASI-graph).

We use the notation $A < B$ in the sense that $A \cap B = \emptyset$. We notice that the relation $<$ is symmetric, but not reflexive and need not be transitive. By the sequence $A_1 < A_2 < A_3 < \dots < A_n$, we mean that the given sets are pairwise disjoint.

The difference set of a set $A$, denoted by $D_A$ is the set of all numerical differences between any two elements of $A$. That is $D_A = \{|a - b| : a, b \in A\}$. The following lemma establishes a necessary and sufficient condition for the cardinality of the sumset $A + B$ of two non-empty sets $A$ and $B$ of integers to be the product of the cardinalities of $A$ and $B$.

**Lemma 1.** [11] Let $A, B$ be two non-empty subsets of $\mathbb{N}_0$. Then, $|A + B| = |A||B|$ if and only if their difference sets, denoted by $D_A$ and $D_B$ respectively, follow the relation $D_A < D_B$ (That is, $D_A \cap D_B = \emptyset$).
**Theorem 2.** [11] Let each vertex $v_i$ of the complete graph $K_n$ be labeled by the set $A_i \in \mathcal{P}(\mathbb{N}_0)$. Then $K_n$ admits a strong IASI if and only if there exists a finite sequence of sets $D_1 < D_2 < D_3 < \dots < D_n$ where each $D_i$ is the difference set of the set-label $A_i$ of the vertex $v_i$.

In other words, a complete graph $K_n$ admits a strong IASI if and only if the difference sets of the set-labels of all vertices of $K_n$ are pairwise disjoint. Hence, as a subgraph of a complete graph, any given graph $G$ admit a strong IASI and hence we have the following theorem.

**Theorem 3.** [11] A connected graph $G$ (on $n$ vertices) admits a strong IASI if and only if each vertex $v_i$ of $G$ is labeled by a set $A_i$ in $\mathcal{P}(\mathbb{N}_0)$ and there exists a finite sequence of sets $D_1 < D_2 < D_3 < \dots < D_m$, where $m \le n$ is a positive integer and each $D_i$ is the set of all differences between any two elements of the set $A_i$.

The relation $<$ of difference sets defined above is called the *difference relation* on $G$. The finite sequence $D_1 < D_2 < D_3 < \dots < D_m$ of difference sets of the set-labels of vertices of a given graph $G$ is called *difference chain of G*.

**Theorem 4.** [11] If a graph $G$ admits a strong IASI, then any subgraph $G_1$ of $G$ also admits strong IASI, which is an IASI induced on $G_1$ by $G$.

In view of the above notions, we have introduced the following notion.

**Definition 3.** [12] The *nourishing number* of a set-labeled graph is the minimum length of the maximal chain of difference sets in $G$. The nourishing number of a graph $G$ is denoted by $\kappa(G)$. That is, the nourishing number of a given graph $G$ is minimum order of the maximal subset of $G$, where the difference relation, of the difference sets of all of whose vertices is an equivalence relation.

**Theorem 5.** [12] *The difference sets of the set-labels of all vertices of a complete graph $K_n$ are pairwise disjoint. That is, the nourishing number of a complete graph $K_n$ is $n$.*

**Remark 1.** Let $G_1$ be a clique in a strong IASI graph $G$. Then by Theorem 4, $G_1$ also admits the induced strong IASI. Then, the set-labels of all vertices of $G_1$ have pairwise disjoint difference sets. Therefore, the nourishing number of a graph $G$ is the minimum order of a maximal complete subgraph of $G$.

Invoking the above remark, the following results have been established.

**Theorem 6.** [12], *The nourishing number of any triangle-free graphs is 2.*

Hence, we have

**Remark 2.** In view of Theorem 6, the *nourishing number of trees, cycles and bipartite graphs* is 2.

A characterisation of strong IASI graphs was done in [11–13]. As an extension to these studies, in this paper, we discuss the nourishing number of certain graph classes and the graph powers.
## 2. New Results

We consider the r-th power of a graph only if r is a positive integer. Now, recall the definition of graph powers.

**Definition 4.** [1] The r-th power of a simple graph G is the graph $G^r$ whose vertex set is V, two distinct vertices being adjacent in $G^r$ if and only if their distance in G is at most r. The graph $G^2$ is referred to as the square of G, the graph $G^3$ as the cube of G.

The following theorem on graph powers is the most relevant result in our present discussion.

**Theorem 7.** [14] If d is the diameter of a graph G, then $G^d$ is a complete graph.

In view of Theorem 7, we proceed to determine the nourishing number of different graph classes and their powers. The following remark provides the nourishing number of complete graphs and their different powers.

**Remark 3.** Any power of a complete graph $K_n$ is $K_n$ itself and hence by Theorem 5, the nourishing number of any power of $K_n$ is n itself.

Hence, we proceed with the study about the nourishing number of a finite powers of complete bipartite graphs.

**Proposition 1.** The nourishing number of the r-th power of a complete bipartite graph is

$$ \varkappa(K_{m,n}^r) = \begin{cases} 2 & \text{if } r = 1 \\ m+n & \text{if } r \ge 2. \end{cases} $$

**Proof.** By Remark 2, the nourishing number of a complete bipartite graph G is 2. The diameter of a complete graph G is 2. Therefore, by Theorem 7, $G^2$ is a complete graph on $m+n$ vertices. Hence, for an IASI defined on the graph $G^r$ and hence the difference sets of the set-labels of all vertices of $G^r$ must be pairwise disjoint. Therefore, $\varkappa(K_{m,n}^r) = m+n$, for $r \ge 2$. □

Now, we study the nourishing number of paths $P_m$ on m vertices. By Theorem 6, the nourishing number of paths is 2. Hence, we need to study the nourishing number of arbitrary powers of paths. The following result determines the nourishing number of the r-th power of a path.

**Theorem 8.** The nourishing number of the r-th power of a path $P_m$ is

$$ \varkappa(P_m) = \begin{cases} r+1 & \text{if } r < m \\ m+1 & \text{if } r \ge m. \end{cases} $$

**Proof.** Let $P_m = v_1v_2v_3...v_n$; $n = m+1$. The diameter of $P_m$ is m. Then by Theorem 7, $P_m^m$ is a complete graph on $m+1$ vertices. Therefore, by Theorem 5, for $r \ge m$, the nourishing number of the r-th power of $P_m$ is $m+1$.
If $r < m$, then for $1 \le i \le n$, the vertices in the set $V' = \{v_i, v_{i+1}, v_{i+2}, \dots, v_{i+r}\}$ are pairwise adjacent and the hence the induced subgraph $\langle V' \rangle$ of $P_m^r$ is a complete graph on $r+1$ vertices. More over, since the vertices $v_i$ and $v_{i+r+1}$ are not adjacent in $P_m^r$, there exists no complete subgraph of order $r+1$ or higher in $P_m^r$. Hence the difference sets of the set-labels of all vertices in $V'$ are pairwise disjoint. Since $i$ is arbitrary, we have the order of a maximal complete subgraph in $P_m^r$ is $r+1$. Therefore, difference sets of at least $r+1$ set-labels of mutually adjacent vertices of $G$ must be pairwise disjoint. Hence, by Theorem 5, the nourishing number of $P_m^r$ is $r+1$. $\square$

We now proceed to discuss nourishing number of finite powers of cycle graphs. By Theorem 6, the nourishing numbers of cycles are also 2. Hence, we need to study about the nourishing number of certain higher integral powers of cycles. The following result discusses the nourishing number of the r-th power of a cycle $C_n$ on $n$ vertices.

**Theorem 9.** The nourishing number of the r-th power of a cycle $C_n$ is

$$ \kappa(C_n) = \begin{cases} r+1 & \text{if } r < \lfloor \frac{n}{2} \rfloor \\ n & \text{if } r \ge \lfloor \frac{n}{2} \rfloor. \end{cases} $$

**Proof.** Let $C_n = v_1v_2v_3\dots v_n v_1$. The diameter of $C_n$ is $\lfloor \frac{n}{2} \rfloor$. Then by Theorem 7, $C_n^{\lfloor \frac{n}{2} \rfloor}$ is a complete graph on $n$ vertices. Therefore, by Theorem 5, for $r \ge \lfloor \frac{n}{2} \rfloor$, the nourishing number of the r-th power of $C_n$ is $n$.

If $r < \lfloor \frac{n}{2} \rfloor$, then for $1 \le i \le n$, the vertices in the set $V' = \{v_i, v_{i+1}, v_{i+2}, \dots, v_{i+r}\}$ are pairwise adjacent in $C_n^r$ and the hence the induced subgraph $\langle V' \rangle$ of $C_n^r$ is a complete graph on $r+1$ vertices. Also, since the vertices $v_i$ and $v_{i+r+1}$ are not adjacent in $C_n^r$, there is no complete subgraph of higher order induced by the set of vertices $\{v_i, v_{i+1}, v_{i+2}, \dots, v_{i+r+1}\}$. Since the choice of $i$ is arbitrary, we have the size of a maximal complete subgraph in $C_n^r$ is $r+1$. Hence, by Theorem 5, the difference sets of the set-labels of all vertices in $V'$ are pairwise disjoint and hence the nourishing number of $C_n^r$ is $r+1$, for any positive integer $r < \lfloor \frac{n}{2} \rfloor$. $\square$

A graph that arises interest in this context is a wheel graph which is defined as follows.

**Definition 5.** [3] A wheel graph, denoted by $W_{n+1}$, is defined as $W_{n+1} = C_n + K_1$.

The nourishing number of finite powers of wheel graphs is determined in the following proposition.

**Proposition 2.** The nourishing number of the r-th power of a wheel graph is

$$ \kappa(W_{n+1}^r) = \begin{cases} 3 & \text{if } r = 1 \\ n+1 & \text{if } r \ge 2. \end{cases} $$

**Proof.** We can determine the nourishing number of $W_{n+1}$ by taking $r = 1$. Let $K_1 = v$ and $C_n = v_1v_2v_3\dots v_n v_1$. For $1 \le i \le n$, three vertices $v, v_i$ and $v_{i+1}$ form a triangle in $W_{n+1}$. Since $v_i$ and $v_{i+2}$ are not adjacent in $W_{n+1}$, this triangle is the maximal clique in $W_{n+1}$, where the set-labels of these three vertices have disjoint difference sets. Therefore, $\kappa(W_{n+1}) = 3$.
Since any two vertices of a wheel graph $W_{n+1}$ are at a distance 2 from each other, the square of it is a complete graph on $n + 1$ vertices. Hence, by Theorem 5, the difference sets of the set-labels of all vertices of $G^2$ are pairwise disjoint. Therefore, $\kappa(W_{n+1}^r) = n + 1$ for all $r \ge 2$. $\square$

Another interesting graph which is related to a wheel graph is a *helm graph* which is defined as follows.

**Definition 6.** [6] A helm graph, denoted by $H_n$, is a graph obtained by adjoining a pendant edge to each of the vertices of the outer cycle of a wheel graph $W_{n+1}$. A helm graph has $2n+1$ vertices and $3n$ edges.

The following theorem discusses the nourishing number of a helm graph and its powers.

**Theorem 10.** *The nourishing number of the r-th power of a helm graph $H_n$ is given by*

$$ \varkappa H_n^r = \begin{cases} 3 & \text{if } r = 1 \\ n + 1 & \text{if } r = 2 \\ n + 4 & \text{if } r = 3 \\ 2n + 1 & \text{if } r \ge 4. \end{cases} $$

**Proof.** Let $u$ be the central vertex, $V = \{v_1, v_2, v_3, \dots, v_n\}$ be the set of vertices of the cycle $C_n$ and $W = \{w_1, w_2, w_3, \dots, w_n\}$ be the set of pendant vertices in $H_n$. In $H_n$, the central vertex $u$ is adjacent to each vertex $v_i$ of $V$ and each $v_i$ is adjacent to a vertex $w_i$ in $W$.

The maximal clique in $H_n$ is a triangle formed by the vertices $vv_iv_{i+1}v$, for $1 \le i \le n$ (in the sense that $v_{n+1} = v_1$), the difference sets of whose set-labels are pairwise disjoint. Therefore, $\varkappa(H_n) = 3$.

Since each vertex $v_i$ in $V$ is adjacent to $u$, the distance between any two vertices in $H_n$ is 2. Hence, the subgraph of $H_n^2$ induced by $V \cup \{u\}$ is a complete graph on $n + 1$ vertices in $H_n^2$. Since the distances between any two $w_i$'s is greater than 2, there is no complete graph of higher order in $H_n^2$. Therefore, $\varkappa(H_n^2) = n + 1$.

Since each vertex $w_i$ in $W$ is at a distance at most 3 from $u$ as well as from all vertices of $V$, for $1 \le i \le n$, the subgraph of $H_n^3$ induced by $V \cup \{u, w_{i-1}, w_i, w_{i+1}\}$ is a complete graph. Since the distances between all other vertices in $W$ and $W_i$ are greater than 3, there is no complete graph of higher order. Therefore, $\varkappa(H_n^3) = n + 4$.

Since $u$ is adjacent all $v_i \in V$, the distance between any two vertices in $H_n$ is 4. Therefore, $H_n^r$; $r \ge 4$ is a complete graph on $2n + 1$ vertices. Hence by Theorem 5, for $r \ge 4$, the nourishing number of $H_n^r$ is $2n + 1$. $\square$

Another graph we consider in this context is a friendship graph whose definition is given below.

**Definition 7.** [6,7] A *friendship graph* $F_n$ is the graph obtained by joining $n$ copies of the cycle $C_3$ with a common vertex. It has $2n + 1$ vertices and $3n$ edges.

The following proposition is about the nourishing number of a friendship graph $F_n$.
**Proposition 3.** The nourishing number of the r-th power of a friendship graph $F_n$ is

$$ \varkappa(F_n^r) = \begin{cases} 3 & \text{if } r = 1 \\ 2n + 1 & \text{if } r \ge 2 \end{cases} $$

**Proof.** The maximal clique in a friendship graph $F_n$ is a triangle. Then, by Theorem 5, $\varkappa(F_n) = 3$. Since all the vertices in $F_n$ at a distance 1 or 2 among themselves, by Theorem 7, $F_n^2$ is a complete graph on $2n + 1$ vertices. Hence, by Theorem 5, $\varkappa(F_n^r) = 2n + 1$, if $r \ge 2$. □

Another similar graph structure is a fan graph which is defined as follows.

**Definition 8.** [5,6] A fan graph, denoted by $F_{m,n}$, is defined as the graph join $\bar{K}_m + P_n$.

**Proposition 4.** The nourishing number of the r-th power of a fan graph $F_{m,n}$ is

$$ \varkappa(F_{m,n}^r) = \begin{cases} 3 & \text{if } r = 1 \\ m + n & \text{if } r \ge 2 \end{cases} $$

**Proof.** The maximal clique in a fan graph $F_{m,n}$ is a triangle. Then, by Theorem 5, $\varkappa(F_n) = 3$. Since all the vertices in $F_{m,n}$ at a distance 1 or 2 among themselves and hence by Theorem 7, $F_{m,n}^2$ is a complete graph on $m + n$ vertices. Hence, by Theorem 5, $\varkappa(F_{m,n}^r) = m + n$ for all $r \ge 2$. □

Now, we proceed to discuss the nourishing number of split graphs and their powers. A split graph is defined as follows.

**Definition 9.** [5] A split graph, denoted by $G(K_r, S)$, is a graph in which the vertices can be partitioned into a clique $K_r$ and an independent set $S$. A split graph is said to be a complete split graph if every vertex of the independent set $S$ is adjacent to every vertex of the clique $K_r$ and is denoted by $K_S(r, s)$, where $r$ and $s$ are the orders of $K_r$ and $S$ respectively.

The following theorem estimates the nourishing number of a split graph.

**Theorem 11.** The nourishing number of the r-th power of a split graph $G = G(K_r, S)^r$ is given by

$$ \varkappa(G^r) = \begin{cases} r & \text{if no vertex of } S \text{ is adjacent to all vertices of } K_r \\ r + 1 & \text{if some vertices of } S \text{ are adjacent to all vertices of } K_r \\ r + l & \text{if } r = 2 \\ r + s & \text{if } r \ge 3; \end{cases} $$

where $l$ is the maximum number of vertices of $S$ which are adjacent to the same vertex of $K_r$ and $s$ is the number of non-isolated vertices in $S$.

**Proof.** Let $G$ be a split graph consisting of a clique $K_r$ and an independent set $S$ that contains $s$ vertices. The isolated vertices in $S$ do not have any impact on the adjacency in the powers of $G$ and hence we need not consider isolated vertices in $S$. Hence, without loss of generality, let $S$ has no isolated vertices in $G$.
If there is no vertex of S which has adjacency with every vertex of $K_r$, then $K_r$ itself is the maximal clique in G and hence $κ(G) = r$.

Assume that some vertices of S are adjacent to all vertices of $K_r$. Let $w_i$ be a vertex in S that is adjacent to every vertex of $K_r$. Then $K_r + \{w_i\}$ is a complete subgraph of G. Since no vertices in S are adjacent among themselves, This subgraph is a maximal clique in G. Therefore, $κ(G) = r + 1$.

Let $S_1 = \{w_1, w_2, \dots, w_l\}$ be the set of vertices in S that are adjacent to a vertex, say $v_i$ in $K_r$. Then each of them is at distance 2 among themselves and from all other vertices of $K_r$. Therefore, $G_1 = K_r \cup S_1$ is a complete graph in $G^2$. Since, $S_1$ is the maximal set of that kind, $G_1$ is a maximal clique in $G^2$. Therefore, $κ(G^2) = r + l$.

All vertices in a split graph G are at a distance at most 3 in G. Therefore, $G^3$ is a complete graph on $r+s$ vertices. Therefore, $κ(G^r) = r+s$, for all values of $r \ge 3$. □

In view of Theorem 11, we establish the following result on complete split graphs.

**Corollary 1.** *The nourishing number of the r-th power of a complete split graph G = $K_S(r, s)$ is given by*

$$κ(G^r) = \begin{cases} r + 1 & \text{if } k = 1 \\ r + s & \text{if } k \ge 2; \end{cases}$$

**Proof.** Since every vertex of S is adjacent to all vertices of $K_r$ in G, by Theorem 11, $κ(G) = r + 1$. Also, in G, being adjacent to all vertices of $K_r$, all vertices in S are at a distance 2 among themselves, $K_r \cup S$ is a complete graph on $r+s$ vertices in $G^2$. Therefore, $κ(G^k) = r+s$ for all $k \ge 2$. □

Another important graph class we need to consider in this context is a sun graph which is defined as follows.

**Definition 10.** [5,7] An *n-sun* or a *trampoline*, denoted by $S_n$, is a chordal graph on $2n$ vertices, where $n \ge 3$, whose vertex set can be partitioned into two sets $U = \{u_1, u_2, u_3, \dots, u_n\}$ and $W = \{w_1, w_2, w_3, \dots, w_n\}$ such that W is an independent set of G and $w_j$ is adjacent to $u_i$ if and only if $j = i$ or $j = i + 1 \pmod n$. A *complete sun* is a sun G where the induced subgraph $\langle U \rangle$ is complete.

The sun graphs with $\langle U \rangle$ is a cycle is one of the most interesting structures among the sun graphs. The following theorem determines the nourishing number of a sun graph G whose non-independent set of vertices induces a cycle in the graph G.

**Theorem 12.** *If G is an *n*-sun graph with $\langle U \rangle = C_n$, then the nourishing number of $G^r$ is given by*

$$κ(G^r) = \begin{cases} 2r + 1 & \text{if } r < \lfloor \frac{n}{2} \rfloor \\ 2(n - 1) & \text{if } r = \lfloor \frac{n}{2} \rfloor \text{ and if } n \text{ is odd} \\ 2n - 1 & \text{if } r = \lfloor \frac{n}{2} \rfloor \text{ and if } n \text{ is even} \\ 2n & \text{if } r \ge \lfloor \frac{n}{2} \rfloor + 1; \end{cases}$$
**Proof.** Let $r < \lfloor \frac{n}{2} \rfloor$, then the subgraph of $G^r$ induced by the vertex set $V' = \{w_{n-r+1}, w_{n-r+2}, w_{n-r+3}, \dots, w_n, v_{n-r+1}, v_{n-r+2}, v_{n-r+3}, \dots, v_n, v_1\}$ is a clique of order $2r + 1$ in $G^r$. Since neither $w_{n-r}$ is adjacent to $v_{i+1}$ nor $w_{n-r+1}$ is adjacent to $v_{i+2}$, this clique is a maximal clique in $G^r$. Therefore, by Theorem 5, $\kappa(G^r) = 2r + 1$.

If $r = \lfloor \frac{n}{2} \rfloor$ and $n$ is odd, then the vertex $w_n$ is adjacent to every vertex of $V$ and to the vertices of $W$ except $w_r$ and $w_{r+1}$. Then, $V' = V \cup [W - \{w_r, w_{r+1}\}]$ induces a maximal clique of order $2n - 2$ in $G$. Therefore, by Theorem 5, if $r = \lfloor \frac{n}{2} \rfloor$ and $n$ is odd, then the nourishing number of $G^r$ is $2(n - 1)$.

If $r = \lfloor \frac{n}{2} \rfloor + 1$ and $n$ is even, then the vertex $w_n$ is adjacent to every vertex of $V$ and to the vertices of $W$ except $w_r$ in $G^r$. Then, $V' = V \cup [W - \{w_r\}]$ induces a maximal clique of order $2n - 1$ in $G^r$. Therefore by Theorem 5, if $r = \lfloor \frac{n}{2} \rfloor$ and $n$ is odd, then the nourishing number of $G^r$ is $2n - 1$.

Since all the vertices in $G = S_n$ are at a distance at most $1 + \lfloor \frac{n}{2} \rfloor$, $G^r$ is a complete graph on $2n$ vertices, where $r \ge 1 + \lfloor \frac{n}{2} \rfloor$. Hence, by Theorem 5, for $r \ge \lfloor \frac{n}{2} \rfloor + 1$, the nourishing number of $G^r$ is $2n$. $\square$

The following theorem discusses the nourishing number of a complete $n$-sun graph.

**Theorem 13.** The nourishing number of a complete $n$-sun graph $G$ is given by

$$ \kappa(G^r) = \begin{cases} n & \text{if } r = 1 \\ n + 1 & \text{if } r = 2 \\ 2n & \text{if } r \ge 3; \end{cases} $$

**Proof.** If $r = 1$, $K_n$ itself is the largest clique in the complete sun graph $G$. Therefore, $\kappa(G) = n$.

Each vertex $w_i$ in the independent set $W$ is adjacent to two vertices of $U$ and is at a distance 2 from all other vertices of $U$. Hence, each vertex $w_i$ is adjacent to all vertices of $U$ in $G^r$. The subgraph of $G^2$ induced by $U \cup \{w_i\}$ is a clique in $G^2$. Since no two vertices in $W$ are at a distance 2, this clique is a maximal clique in $G^2$. Therefore, $\kappa(G^2) = n + 1$.

Since all vertices in $G$ are at a distance at most 3, the cube and higher powers of $G$ are complete graphs on $2n$ vertices. Therefore, by 5, $\kappa(G^r) = 2n$ for $r \ge 3$. $\square$

Another important graph involving cycle graphs is a sunlet graph. An $n$-sunlet graph is defined as follows.

**Definition 11.** [7] The $n$-sunlet graph is the graph on $2n$ vertices obtained by attaching one pendant edge to each vertex of a cycle $C_n$.

The following result discusses about the nourishing number of an $n$-sunlet graph.

**Theorem 14.** The nourishing number of the $r$-th power of an $n$-sunlet graph $G$ is

$$ \kappa(G^r) = \begin{cases} 2r & \text{if } r < \lfloor \frac{n}{2} \rfloor + 1 \\ 2(n-1) & \text{if } r = \lfloor \frac{n}{2} \rfloor + 1 \text{ and } n \text{ is odd} \\ 2n-1 & \text{if } r = \lfloor \frac{n}{2} \rfloor + 1 \text{ and } n \text{ is even} \\ 2n & \text{if } r \ge \lfloor \frac{n}{2} \rfloor + 2. \end{cases} $$
**Proof.** The proof of this proposition is similar to the proof of Theorem 12. Let $V = \{v_1, v_2, v_3, \dots, v_n\}$ be the vertex set of the cycle $C_n$ and $W = \{w_1, w_2, w_3, \dots, w_n\}$ be the set of pendant vertices in $G$.

If $r < \lfloor \frac{n}{2} \rfloor + 1$, the vertex set $V' = \{w_{n-r+2}, w_{n-r+3}, w_{n-r+4}, \dots, w_n, v_{n-r+1}, v_{n-r+2}, v_{n-r+3}, \dots, v_n, v_1\}$ induces a clique in $G$ on $2r$ vertices. Since there is no other vertex outside $V'$ which is at a distance at most $r$ from all vertices in $V'$, the induced graph $\langle V' \rangle$ is a maximal clique in $G^r$. Therefore, for $r < 1 + \lfloor \frac{n}{2} \rfloor$, $\kappa(G) = 2r$.

If $r = \lfloor \frac{n}{2} \rfloor + 1$ and $n$ is odd, then the vertex $w_n$ is adjacent to every vertex of $V$ and to the vertices of $W$ except $w_r$ and $w_{r+1}$. Then, $V' = V \cup [W - \{w_r, w_{r+1}\}]$ induces a maximal clique of order $2n - 2$ in $G$. Therefore, in this case, the nourishing number of $G^r$ is $2(n - 1)$.

If $r = \lfloor \frac{n}{2} \rfloor + 1$ and $n$ is even, then the vertex $w_n$ is adjacent to every vertex of $V$ and to the vertices of $W$ except $w_r$ in $G^r$. Then, $V' = V \cup [W - \{w_r\}]$ induces a maximal clique of order $2n - 1$ in $G^r$. Therefore, in this case, the nourishing number of $G^r$ is $2n - 1$.

Since the maximum distance between the vertices in $W$ is $2 + \lfloor \frac{n}{2} \rfloor$, diameter of $G$ is $2 + \lfloor \frac{n}{2} \rfloor$. Hence, by Theorem 7, $G^r$ is a complete graph for all $r \ge 2 + \lfloor \frac{n}{2} \rfloor$ on $2n$ vertices. Therefore, the difference sets of the set-labels of all vertices of $G^r$ are pairwise disjoint. Hence, for $r \ge 2 + \lfloor \frac{n}{2} \rfloor$ the nourishing number of $G^r$ is $2n$. $\square$

### 3. Conclusions

In this paper, we have established some results on the nourishing number of certain graphs and graph powers. The admissibility of strong IASI by various other graph classes, graph operations and graph products and finding the corresponding nourishing numbers are open. Determining the nourishing numbers of powers of bipartite graphs, chordal graphs, crown graphs, prism graphs etc. are some of the open problems.

Besides the above-mentioned problems, there are several other graph classes and structures for which the admissibility of strong IASIs are yet to be verified and the corresponding nourishing numbers are to be determined. More over, the properties and characteristics of strong IASIs, both uniform and non-uniform, are yet to be investigated. The problems of establishing the necessary and sufficient conditions for various graphs and graph classes to have certain IASIs are also open.

### Acknowledgments

The authors would like to thank the anonymous reviewers for their insightful suggestions and critical and constructive remarks which made the overall presentation of this paper better.

### Author Contributions

Both authors contributed significantly in writing this article. Both authors read and approved the final manuscript.

### Conflicts of Interest

The authors declare no conflict of interest regarding the publication of this paper.
References

1. Bondy, J.A.; Murty, U.S.R. *Graph Theory*; Springer: Berlin, Germany, 2008.

2. Chartrand, G.; Zhang, P. *Introduction to Graph Theory*; McGraw-Hill Inc.: New York, NY, USA, 2005.

3. Harary, H. *Graph Theory*; Addison-Wesley Publishing Company Inc.: Boston, MA, USA, 1994.

4. West, D.B. *Introduction to Graph Theory*; Pearson Education Inc.: Upper Saddle River, NJ, USA, 2001.

5. Brandstädt, A.; Le, V.B.; Spinard, J.P. *Graph Classes: A Survey*; SIAM: Philadelphia, PA, USA, 1999.

6. Gallian, J.A. *A Dynamic Survey of Graph Labeling*. *Electron. J. Comb.* **2013**, #DS6.

7. Information System on Graph Classes and Their Inclusions. Available online: http://www.graphclasses.org (accessed on 22 February 2015).

8. Nathanson, M.B. *Additive Number Theory: Inverse Problems & Geometry of Sumsets*; Springer: Berlin, Germany, 1996.

9. Germina, K.A.; Anandavally, T.M.K. Integer Additive Set-Indexers of a Graph: Sum Square Graphs. *J. Comb. Inf. Syst. Sci.* **2012**, *37*, 345–358.

10. Germina, K.A.; Sudev, N.K. On Weakly Uniform Integer Additive Set-Indexers of Graphs. *Int. Math. Forum* **2013**, *8*, 1827–1834.

11. Sudev, N.K.; Germina, K.A. Some New Results on Strong Integer Additive Set-Indexers of Graphs. *Discret. Math. Algorithms Appl.* **2015**, *7*, doi:10.1142/S1793830914500657.

12. Sudev, N.K.; Germina, K.A. A Characterisation of Strong Integer Additive Set-Indexers of Graphs. *Commun. Math. Appl.* **2014**, *5*, 91–100.

13. Sudev, N.K.; Germina, K.A. On Integer Additive Set-Indexers of Graphs. *Int. J. Math. Sci. Eng. Appl.* **2014**, *8*, 11–22.

14. Weisstein, E.W. *CRC Concise Encyclopedia of Mathematics*; CRC Press: Boca Raton, FL, USA, 2011.

© 2015 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/).