Prime Distance Graphs and Applications of Graph Labeling: A Modelling Approach - Ajaz Ahmad Pir; A. Parthiban (Recent Advances in Mathematical Research and Computer Science Vol. 10, 2022)
A graph H is a prime distance graph if there exists an one-to-one function h : V (H ) \(→\) Z such that for any two adjacent vertices x and y, the integer |h(x) - h(y)| is a prime. So H is a prime distance graph if and only if there exists a prime distance labeling of H. If the edge labels of H are also distinct, then h becomes a distinct prime distance labeling of H and H is called a distinct prime distance graph. The generalized Petersen graphs P (n, k) are defined to be a graph on 2n (n \(\) 3) vertices with V (P (n, k)) = vi , ui : 0 \(\) i \(\)n - 1 and E(P (n, k)) = vi vi+1 , vi ui , ui ui+k : 0 \(\) i \(\) n - 1, subscripts modulo n. In this chapter, we give a concise overview on these two labeling, specifically, highlight that the generalized Petersen graphs P (n, 3) permit a prime distance labeling for all even n > 5 and conjecture that P (n, 2) and P (n, 3) admit a prime distance labeling for any n \(\) 5 and all odd n \(\) 5, respectively. Moreover, the cycle Cn admits a distinct prime distance labeling for all n \(\) 3.