Volume 3, Issue 2, August 2019, Pages: 34-52
V. Yegnanarayanan
School of Humanities and Sciences, SASTRA University, Thanjavur-613401, TN, India
Stimulated by the famous plane coloring problem Eggleton coined the term distance graph and studied widely the prime distance graphs. A prime distance graph (PDG) G(Z;D) is one whose vertex set V is the set of integers Z and the distance set D is a subset of the set of primes P . The edge set of G denoted E is the one whose elements (u; v) for any u; v ∊ V (G) are characterized by the property that d(u; v) ∊ D where d(u; v) = |u-v|. According to J.D.Laison, C. Starr and A. Walker a graph G is a PDG if there exists a 1-1 labeling f : V (G) → Z such that for any two adjacent vertices u and v the integer |f(u)-f(v)| is a prime. Further they called such a labelling of V(G) a prime distance labelling (PDL) of G. In this paper we prove certain existence and non-existence results concerning PDG and PDL and study the relationship between them. We also discuss certain applications besides raising some open problems.
Prime Distance Graph; Prime Distance Labeling; Chromatic number; Pythagorean number; Pythagorean triples and Pythagorean quadruples.
[1] Anthony B. Evans, Gerd H. Fricke, Meneri Carl C, Mckee Terry A, Manley Perkel. Representations of Graphs
Modulo n. J. Graph Theory 1994; 18(8): 801-815.
[2] Barning FJM. On Pythagorean and quasi-Pythagorean triangles and a generation process with the help of unimodular matrices, (Dutch) Math. Centrum Amsterdam Afd. Zuivere Wisk, ZW-011, 1963.
[3] Benoit R. Kloeckner. Coloring distance graphs: a few answers and many questions by hal Id: hal-00821852
https://hal.archives-ouvertes.fr/hal-00821852 Submitted on 13 May 2013.
[4] Bondy JA, Murty USR. Graph Theory with Applications. The Macmillan Press Ltd., (1976).
[5] Billingely. Prime Numbers and Brownian motion. Amer. Math. Monthly 1973; 80: 1099-1115.
[6] Broersma HJ, Duijvestijn AJW, Gobel F. Generating all 3-connected 4-regular graphs from the octahedron graph.
Journal of Graph Theory 1993; 17(5): 613-620.
[7] Chang GJ, Chen JJ, Huang K-Ch. Integral distance graphs. J. Graph Theory 1997; 25: 287-294.
[8] Chilakamarri KB. Unit-distance graphs in Minkowski metric spaces. Geom. Dedicata 1991; 37(3): 345-356.
[9] Chromatic number of the plane & its relatives, history, problems and results: an essay in 11 parts, Ramsey theory,
Progr. Math., vol. 285, Birkhauser/Springer, New York, 2011, 121-161.
[10] Clement PA. Congruences for sets of primes. The American Mathematical Monthly 1949; 56(1): 23-25.
[11] Datta B, Singh AN. History of Hindu Mathematics, A Source Book, Parts 1 and 2, (single volume), Asia Publishing
House, Bombay, 1962.
[12] de Bruijn NG, Erdos P. A colour problem for infnite graphs and a problem in the theory of relations. Indagationes
Math. 1951; 13: 369-373.
[13] (ed.)-Ramsey theory, Progress in Mathematics, vol. 285, Birkhauser/Springer, New York, 2011. DISTANCE
GRAPHS 17.
[14] Eggleton RB, Erdos P, Skilton DK. Coloring the real line. J. Combin. Theory (B) 1985; 39: 86-100.
[15] Eggleton RB, Erdos P, Skilton DK. Coloring prime distance graphs. Graphs and Combinatorics 1990; 6: 17-32.
[16] Erdos P. On some extremal problems in graph theory. Israel. J. Math. 1965; 3: 113-116.
[17] Falconer KJ. The realization of distances in measurable subsets covering Rn. J. Combin. Theory Ser. A 1981; 31(2):
184-189.
[18] Harary F. Graph Theory, Addisson-Wesley Publishing Company, Reading, 1969.
[19] Jensen TR, Toft B. Graph coloring problems, John Wiley & Sons, New York, 1995.
[20] Jerrold R. Griggs, Roger K. Yeh. labelling Graphs with a condition at distance 2. SIAM J. Discrete. Math. 1992;
5(4): 586-595.
[21] Johnson Jr PD, Szlam AD. A new connection between two kinds of Euclidean coloring problems. Geombinatorics
2001; 10(4): 172-178.
[22] Josua D, Laison, Colin Starr, Andrea Walker. Finite prime distance graphs and 2-odd graphs. Discrete. Math 2013;
313(20): 2281-2291.
[23] Kahle M. chromatic number of the hyperbolic plane, MathOverow, 2012, http://mathoverow.net/questions/86234/
[24] Kak S. The structure of the Rgveda. Indian Journal of History of Science 1993; 28: 71-79.
[25] Kak S. The Asvamedha: The Rite and its Logic, Motilal Banarsidass, Delhi, 2002.
[26] Kak S, Shulba Sutras. In Encyclopedia of India (edited by Stanley Wolpert). Charles Scribner's Sons/Gale, New York, 2005.
[27] Kak S. Early record of divisibility and primality, arXiv:0904.1154
[28] Kak S. Aryabhata's mathematics, arXiv:1002.3409
[29] Kemnitz A, Kolberg H. Chromatic number of integer distance graphs. Discrte. Math 1998; 191: 113-123.
[30] Lec 6 | MIT 6.042J Mathematics for Computer Science, Fall 2010 | Video Lecture.
[31] Marek Wolf, Random walk on the prime numbers, Physica A (1998), 335-344.
[32] Matteo Arpe. The Rule behind the occurrence of prime numbers. Italian Journal of Pute and Applied Mathematics 2008; N-23: 1-16.
[33] McCullough D. Height and excess of Pythagorean triples. Mathematics Magazine. 2005; 78: 26-44.
[34] Neugebauer O, Sachs A. Mathematical Cuneiform Texts, New Haven, CT., 1945.
[35] O'Conner JJ, Robertson EF, Baudhayana. History of Mathematics Project. http://wwwhistory.mcs.st-
and.ac.uk/ history/Biographies/Baudhayana.html
[36] Rao TRN, Kak S. Computing Science in Ancient India, Munshiram Manoharlal, New Delhi, 2000.
[37] Roberts FS. From Garbage to Rainbows: Generalizations of Graph Coloring and their Applications. In Alavi, Y.,
Chartrand, G., Oellermann, O.R. , and Schwenk, A.J. (eds.), Graph Theory, Combinatorics, and Applications.
Wiley, New York, 1991.
[38] Seidenberg A. The origin of mathematics. Archive for History of Exact Sciences 1978; 18: 301-342.
[39] Sen SN, Bag AK. The Sulbasutras. Indian National Science Academy, New Delhi, 1983.
[40] Shelah S, Soifer A. Axiom of choice and chromatic number of the plane. J. Combin. Theory Ser. A 2003; 103(2):
387-391
[41] Simmons GJ. The chromatic number of the sphere. J. Austral. Math. Soc. Ser. A. 1976; 21(4): 473-480.
[42] Soifer A. The mathematical coloring book, Springer, New York, 2009, Mathematics of coloring and the colorful life
of its creators, With forewords by Branko Grunbaum, Peter D. Johnson, Jr. and Cecil Rousseau.
[43] Srinivasiengar CN. The History of Ancient Indian Mathematics, The World Press, Calcutta, 1967.
[44] Supriya Mohanty, Mohanty SP. Pythagorean numbers. Fibonacci Quaterly 1990; 28: 31-42.
[45] Van der Waerden BL. Science Awakening, Oxford University Press, 1971.
[46] Voigt M. Coloring of distance graphs. Ars Combin 1999; 52: 3-12.
[47] Voigt M, Walther H, Chromatic number of iprime distance graphs. Discrete. App. Math 1994; 51: 197-209.
[48] Walther H. Uber eine spezielle Klasse unendilicher Graphen, Graphenthorie II (Klauss Wagner and Rainer Bo-
dendiek, eds) Bibliographisches Institut Wissenschaftsverlag 1990; 268-295 (German).
[49] Zhu Z. Distance graphs in the real line. Manuscript, 1996.
[50] Zvi Retchiman Konigberg. Generator and Verification Algorithms for prime k-tuples using Binomial Expressions.
International Mathematical Forum 2011; 6: 2169-2178.
