Mathematics and Statistics Vol. 12(3), pp. 229 - 233
DOI: 10.13189/ms.2024.120302
Reprint (PDF) (331Kb)

On Questions Concerning Finite Prime Distance Graphs

Ram Dayal 1, A. Parthiban 2,*, P. Selvaraju 3
1 Department of Mathematics, Lovely Professional University, Phagwara 144 411, Punjab, India
2 Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Vellore, India
3 Department of Mathematics, Rajalakshmi Institute of Technology, Chennai, India


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.

Prime Distance Labeling, Prime Distance Graph, Goldbach’s Conjecture, Twin Prime Conjecture

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Ram Dayal , A. Parthiban , P. Selvaraju , "On Questions Concerning Finite Prime Distance Graphs," Mathematics and Statistics, Vol. 12, No. 3, pp. 229 - 233, 2024. DOI: 10.13189/ms.2024.120302.

(b). APA Format:
Ram Dayal , A. Parthiban , P. Selvaraju (2024). On Questions Concerning Finite Prime Distance Graphs. Mathematics and Statistics, 12(3), 229 - 233. DOI: 10.13189/ms.2024.120302.