Log-linear algorithm to generate prime trees
Karnam Gurunadhan Tharunrajtharunrajkg1436@gmail.comDepartment of MathematicsSchool of Advanced SciencesVellore Institute of TechnologyVellore, Tamil Nadu, 632014, India0009-0001-3479-852XView full profile → , *P. RagukumarCorresponding authorragukumar2003@gmail.comDepartment of MathematicsSchool of Advanced SciencesVellore Institute of TechnologyVellore, Tamil Nadu, 632014, India0000-0002-2923-3268View full profile →
* Corresponding author · click or hover a name for details
- Received:
- 11 Jun 2025
- Published Online:
- 05 Mar 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-2176
- Pages:
- 2635–2649
Abstract
A graph G is considered to have a prime labeling when each of its |V| vertices is assigned a unique label from the set {1, 2, 3, 4, …,|V|}, ensuring that the labels of any two connected vertices are coprime. In 1980, Roger Entringer proposed the conjecture that ``All trees have a Prime labeling”, which is not settled till today. In spite of many researchers working on prime labeling, conjecture on prime trees is still open. Up to our knowledge, no one has given an algorithm to generate prime trees. In this paper, given an arbitrary tree T, we develop an algorithm to construct a prime labeled tree T’ such that T is a subtree of T’. We extend this algorithm for k arbitrary trees Ti, where i = 1, 2, 3, …, k to construct a larger prime labeled tree T’ such that each Ti is a subtree of T’. We also develop a log-linear algorithm to construct a larger prime labeled tree T’ from k prime trees Ti, where i = 1, 2, 3, …, k such that Ti is a subtree of T’. Further, we prove the correctness of the proposed algorithms and obtain the time complexity of the proposed algorithms.
Keywords
Subject Classifications
References
[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. London, U.K.: Macmillan (1976).
[2] H. L. Fu and K. C. Huang, “On prime labellings,” Discrete Mathematics, vol. 127, no. 1–3, pp. 181–186 (1994).
[3] J. A. Gallian, “A dynamic survey of graph labeling,” Electronic Journal of Combinatorics, vol. 6, no. DS6, pp. 1–623 (2022).
[4] O. Pikhurko, “Trees are almost prime,” Discrete Mathematics, vol. 307, no. 11–12, pp. 1455–1462 (2007).
[5] L. Robertson and B. Small, “On Newman’s conjecture and prime trees,” (2009).
[6] A. Rosa, “On certain valuations of the vertices of a graph,” in Theory of Graphs (International Symposium, Rome, July 1966). New York, NY, USA: Gordon and Breach, pp. 349–355 (1967).
[7] H. Salmasian, “A result on prime labelings of trees,” Bulletin of the Institute of Combinatorics and its Applications, vol. 28, pp. 36–38, 2000).
[8] A. Tout, A. N. Dabboucy, and K. Howalla, “Prime labeling of graphs,” National Academy Science Letters, vol. 11, pp. 365–368 (1982).
