Weak Set-Labeling Number of Certain IASL-Graphs

Abstract

Let ${\mathbb{N}}_0$ be the set of all non-negative integers, let $X\subset {\mathbb{N}}_0$ and $\mathcal{P}(X)$ be the the power set of $X$. An integer additive set-labeling (IASL) of a graph $G$ is an injective function $f:V(G)\to \mathcal{P}({\mathbb{N}}_0)$ such that the induced function $f^{+}:E(G)\to \mathcal{P}({\mathbb{N}}_0)$ is defined by $f^{+}(uv)=f(u)+f(v)$, where $f(u)+f(v)$ is the sum set of $f(u)$ and $f(v)$. An IASL $f$ is said to be an integer additive set-indexer (IASI) of a graph $G$ if the induced edge function $f^{+}$ is also injective. An integer additive set-labeling $f$ is said to be a weak integer additive set-labeling (WIASL) if $|f^{+}(uv)|=\max (|f(u)|,|f(v)|)\forall uv\in E(G)$. The minimum cardinality of the ground set $X$ required for a given graph $G$ to admit an IASL is called the set-labeling number of the graph. In this paper, we introduce the notion of the weak set-labeling number of a graph $G$ as the minimum cardinality of $X$ so that $G$ admits a WIASL with respect to the ground set $X$ and discuss the weak set-labeling number of certain graphs.

8 figures, Published