Further Results On SD-prime Labeling

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’ : E(G) \to \{0, 1\} \) such that for any edge \( uv \) in \( E(G) \), \( f'(uv) = 1 \) if \(\gcd(S, D) = 1\), and \( f'(uv) = 0 \) otherwise. Such a labeling is called an SD-prime labeling if \( f'(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 \emph{strongly SD-prime graph} 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.