On Questions Concerning Finite Prime Distance Graphs

Graph labeling is an allocation of labels (mostly integers) to the nodes/lines or both of a graph G α subject to a few conditions.The field of graph theory, specifically graph labeling, plays a vital role in various fields.To name a few, graph labeling is utilized in coding, x-ray crystallography, radar, astronomy, circuit design, communication network addressing, and data base management.It can also be applied to network security, network addressing, channel assignment process, and social networks.A graph G β is a prime distance graph (PDG) if its nodes can be assigned with distinct integers such that for any two adjacent nodes, the positive difference of their labels is a prime number.A complete characterization of prime distance graphs is an open problem of high interest.This paper contributes partially towards the same.More specifically, Laison et al. raised the following questions.(1) Is there a family of graphs which are PDGs if and only if Goldbach's Conjecture is true?(2) What other families of graphs are PDGs?In this paper, these questions are answered partially and also show certain families of graphs that admit prime distance labeling (PDL) if and only if the Twin Prime Conjecture holds, besides establishing PDL of some special graphs.