Prime and odd prime labelings of several graph classes

Hafif Komarullah, Vira Hari Krisnawati, Kristiana Wijaya, Noor Hidayat

Abstract


A prime labeling of a graph is an assignment of distinct integers to its vertices such that any two adjacent vertices are labeled with numbers that are relatively prime. An odd prime labeling is a variant in which the labels are restricted to odd integers while still preserving the coprimality condition. Motivated by the odd prime graph conjecture, which asserts that every prime graph is odd prime, we study prime and odd prime labelings on various classes of graphs. We construct explicit labeling functions and prove that comb graphs, disjoint unions of comb graphs, triangular book graphs, and modified triangular book graphs K1,1,n ⊙ 2Sm admit both prime and odd prime labelings. We further establish an odd prime labeling for torch graphs, extending a known prime labeling result for this class. Consequently, all graph families considered in this paper satisfy the odd prime graph conjecture. These results expand the collection of graphs known to admit odd prime labelings and provide additional evidence supporting the conjecture.

Keywords


comb graph; odd prime labeling; prime labeling; torch graph; triangular book graph.

Full Text:

PDF

DOI: http://dx.doi.org/10.19184/ijc.2026.10.1.6

References

J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 6(25) (2022), 4–623.

N. L. Prasanna, K. Sravanthi and N. Sudhakar, Applications of graph labeling in communication networks, Orient. J. Comput. Sci. Technol. 7(1) (2014), 139–145.

J. R. Griggs and R. K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5(4) (1992), 586–595.

M. Aigner and E. Triesch, Codings of graphs with binary edge labels, Graphs Combin. 10(1) (1994), 1–10.

A. C. Prihandoko, D. Dafik and I. H. Agustin, Implementation of super H-antimagic total graph on establishing stream cipher, Indones. J. Combin. 3(1) (2019), 14–23.

A. Elumalai, Graph coloring and labeling applications in computer science, Malaya J. Math. Suppl. 2 (2020), 2039–2041.

R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs, SIAM J. Algebraic Discrete Methods 1(4) (1980), 382–404.

A. Rosa, On certain valuations of the vertices of a graph, in Theory of Graphs, International Symposium, Rome, Italy, Gordon and Breach, New York, 1967, 349–355.

J. Sedláček, On magic graphs, Math. Slovaca 26(4) (1976), 329–335.

R. Tout, A. N. Dabboucy and K. Howalla, Prime labeling of graphs, Nat. Acad. Sci. Lett.-India 5(11) (1982), 365–368.

M. A. Seoud, A. T. Diab and E. A. Elsahawi, On strongly-C harmonious, relatively prime, odd graceful and cordial graphs, Proc. Math. Phys. Soc. Egypt 73 (1998), 33–55.

M. A. Seoud and M. Z. Youssef, On prime labeling of graphs, Congr. Numer. 141 (1999), 203–215.

S. N. Rao, Prime labelling, in RC Bose Centenary Symposium on Discrete Mathematics and Applications, Kolkata, India, 2002.

O. Pikhurko, Trees are almost prime, Discrete Math. 307(11–12) (2007), 1455–1462.

M. Z. Youssef and E. A. Elsakhawi, Some properties of prime graphs, Ars Combin. 84 (2007), 129–140.

L. Robertson and B. Small, On Newman's conjecture and prime trees, Integers 9(2) (2009), 117–128.

U. M. Prajapati and S. J. Gajjar, Prime labeling of generalized Petersen graphs, Int. J. Math. Soft Comput. 5 (2015), 65–71.

E. Ghorbani and S. Kamali, Prime labeling of ladders, arXiv preprint arXiv:1610.08849 (2016).

L. K. Wilson and H. Jini, Prime labeling of torch graph, Malaya J. Matematik 9(1) (2021), 890–895.

U. Prajapati and K. P. Shah, On odd prime labeling, Int. J. Res. Anal. Rev. 5(4) (2018), 284–294.

M. Youssef and Z. Almoreed, On odd prime labeling of graphs, Open J. Discrete Appl. Math. 3 (2020), 33–40.

H. Carter and N. B. Fox, Odd prime graph labelings, arXiv preprint arXiv:2208.08488 (2022).

S. Meena and G. Gajalakshmi, Odd prime labeling of graphs related to circular ladder, Commun. Math. Appl. 13(4) (2022), 1307–1315.

H. Komarullah, N. Hidayat, V. H. Krisnawati and K. Wijaya, Prime and odd prime labelings on cycle-related graphs, Sci. Technol. Indones. 11(2) (2026), 551–558.

H. Komarullah, N. Hidayat, V. H. Krisnawati and K. Wijaya, Prime and odd prime labelings of broom graphs and some related graphs, Pan-Am. J. Math. 5 (2026), 9.

Sukirman, Teori Bilangan, Universitas Terbuka, Tangerang Selatan, 2016.

H. Komarullah, Slamin and K. Wijaya, A minimum coprime number for amalgamation of wheel, in Proc. International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021), 2022, 53–57.


Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats