Further Results On $SD$-prime Labeling

Abstract

Let $G=(V(G),E(G))$ be a simple, finite, and undirected graph with $n$ vertices. Given a bijection $f:V(G)\to \{1,\dots ,n\}$, one can associate two integers $S=f(u)+f(v)$ and $D=|f(u)–f(v)|$ with every edge $uv\in E(G)$. The labeling $f$ induces an edge labeling $f^{\prime }:E(G)\to \{0,1\}$ such that for any edge $uv$ in $E(G)$, $f^{\prime }(uv)=1$ if $gcd(S,D)=1$, and $f^{\prime }(uv)=0$ otherwise. Such a labeling is called an SD-prime labeling if $f^{\prime }(uv)=1$ for all $uv\in E(G)$. We say that $G$ is SD-prime if it admits an SD-prime labeling. A graph $G$ is said to be a $stronglySD-primegraph$ if for every vertex $v$ of $G$ there exists an SD-prime labeling $f$ satisfying $f(v)=1$. In this paper, we first give some sufficient conditions for a theta graph to be strongly SD-prime. We then provide constructions of new SD-prime graphs from known SD-prime graphs and investigate the SD-primality of some general graphs.