ON SOME FAMILIES OF LINEAR DIOPHANTINE GRAPHS

Year 2025, Volume: 15 Issue: 11, 2674 - 2686, 03.11.2025

Omar Mohamed Salama Mohammed Abd El Azim Seoud Mohamed Anwar , Ahmed Elsonbaty

Abstract

Linear Diophantine labeling of graphs is an extension of the prime labeling of graphs. In this manuscript, we introduce some necessary conditions for determining whether a given graph admits linear Diophantine labeling or not, and if yes, we will find such a linear Diophantine labeling. We also study specific families of graphs, including the Complete graphs $K_n$, Wheel graphs $W_n$ and $W_{n,n}$, Circulant graphs $C_n(j)$, Path graphs $P_n(j)$, Cartesian product graphs $C_3 \times C_m$, Normal Product graphs $P_{n}\circ P_{n} $, Corona graphs $G\odot H$, Double Fan graphs $g_n=P_n+\overline{K_2}$, Power graphs $P^2_n$ and $P^3_n$, to ascertain their Diophantine nature.

Keywords

Graph labeling , Prime labeling , Diophantine labeling , Families of Diophantine graphs

Thanks

The authors would like to express their gratitude to the referees for their insightful comments and valuable suggestions, which have greatly improved this manuscript.

References

• Bickle, A., (2020), Fundamentals of Graph Theory, American Mathematical Society, Providence, Rhode Island, USA, vol.43, pp. 336.
• Bondy, J. A., Murty, U. S. R., (2008), Graph Theory, Graduate Texts in Mathematics, vol.244, Springer, p.82, ISBN 9781846289699.
• Burton, D. M., (2011), 7th ed, Elementary number theory, A business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas, New York.
• Deretsky, T., Lee, S. M., Mitchem, J., (1991), On vertex prime labeling of graphs in graph theory, Combinatorics and Applications vol. I. J., Alavi, Chartrand G., Ollerman O., Schwank A., 6th ed., International Conference Theory and Application of Graphs, Wiley, New York, pp. 359-369.
• Elsonbaty, A., Daoud, S., (2017), Edge even graceful labeling of some path and cycle related graphs, Ars Combinatorial.
• El Harbi, E., (2018), Number Theoretic Functions and Graph Labeling, Published M.Sc. thesis.
• Fu, H. L., Huang, K. C., (1994), On Prime Labeling, Discrete Mathematics, vol. 127, No. 1-3, PP. 181-186, doi:10.1016/0012-365X(92)00477-9.
• Gallian, J. A., (2007), A dynamic survey of graph labeling, The Electronic Journal of Combinatorics.
• Gross, J. L., Yellen, J., Zhang, P.,\ $2^{nd}$ edition, Handbook of Graph Theory, Version Date: 20130923, International Standard Book Number-13:978-1-4398-8019-7.
• Hoshino, R., (2007), Independence polynomials of circulant graph, Published Ph.D. thesis, Dalhousie University, Halifax, Nova Scotia.
• Harary, F., (1969), Graph Theory, Addison-Wesley Publishing Company, Reading, Massachusetts.
• Lee, S. M., Wui, I., Yeh, J., (1988), On the Amalgamation of Prime Graphs, Bulletin of the Malaysian Mathematical Sciences Society, Second Series, vol. 11, pp. 59-67.
• Mahran, A. E. A., (2008), Some different treatments of graph Labeling, Published M.Sc. thesis, Ain Shams University, Cairo.
• Rosa, A., (1967), On certain valuations of the vertices of a graph, Theory of Graphs, Intl., Symp., Rome 1966, Gordon and Breach, Dunod, Paris, pp. 349–355.
• Rosen, K. H., $5^{th}$ edition, Elementary Number Theory and Its Applications, Addison-Wesley Publishing Company, Reading Massach.
• Ramanujan, S., (1919), Proof of Bertrand’s postulate, Journal of the Indian Mathematical Society.
• Robert, A. M., (2000), A Course in p-adic Analysis, Springer Science Business Media, LLC.
• Sondow, J., (2009), Ramanujan primes and Bertrand's postulate, The American Mathematical.
• Seoud, M. A., Youssef, M. Z., (1999), On Prime Labeling of Graphs, Congressus Numerantium, vol. 141, pp. 203-215.
• Seoud, M. A., Anwar, M., Nasr, A., Elsonbaty, A., (submitted for publication), Some Necessary and Sufficient Conditions for Diophantine Graphs.
• Tout, A., Dabboucy, A. N., Howalla, K., (1982), Prime Labeling of Graphs, National Academy Science Letters, vol. 11, pp. 365-368.
• Weisstein, Eric, W., (1990), Graph Power (https://mathworld.wolfram.com/GraphPower.html), Skiena, P. 229.
• Youssef, M. Z., (2000), On graceful harmonious and prime labeling of graphs, Published Ph.D. thesis, Ain Shams University, Cairo.