The Sparing Number of Certain Graph Powers

Abstract

An integer additive set-indexer is defined as an injective function $f:V(G)\to 2^{{\mathbb{N}}_0}$ such that the induced function $g_f:E(G)\to 2^{{\mathbb{N}}_0}$ defined by $g_f(uv)=f(u)+f(v)$ is also injective. An IASI $f$ is said to be a weak IASI if $|g_f(uv)|=max(|f(u)|,|f(v)|)$ for all $u,v\in V(G)$. A graph which admits a weak IASI may be called a weak IASI graph. The set-indexing number of an element of a graph $G$, a vertex or an edge, is the cardinality of its set-labels. The sparing number of a graph $G$ is the minimum number of edges with singleton set-labels, required for a graph $G$ to admit a weak IASI. In this paper, we study the admissibility of weak IASI by certain graph powers and their sparing numbers.

14 pages, 6 figures, submitted