Research Article | | Peer-Reviewed

Prime Labeling of Mobius Ladder Graphs Mn

Received: 16 April 2026     Accepted: 3 May 2026     Published: 18 November 2026
Views:       Downloads:
Abstract

Graph labeling, in which integers are assigned to the vertices or edges of a graph subject to given conditions, is an active area of graph theory, and prime labeling is one of its well-studied variants. Let G=(V,E) be a graph with vertex set V and edge set E. A graph G is said to have a prime labeling if its vertices can be labeled with distinct integers from 1,2,…,|V| such that for every edge xy in G, the labels assigned to x and y are relatively prime or coprime. A graph is called prime if it has a prime labeling. The Mobius ladder Mn is the graph on 2n vertices (n≥ 3) formed by two paths v0,v1,…,vn-1 and u0,u1,…,un-1, the n rungs viui, and the two crossing edges un-1v0 and vn-1u0. Seoud and Youssef proved that Mn is not prime for even n. In this paper, we study the prime labeling of the Mobius ladder Mn for odd n. We first show that M3 is not prime. We then define explicit labeling functions for sixteen classes of odd n and prove that each function is a prime labeling by means of simple sufficient conditions for two labels to be coprime, for example that one label equals 1, that their sum is prime, or that their difference is 1 or a suitable prime power. Examples of the resulting labelings are illustrated in figures. Since every odd n with 5≤ n≤ 2001 belongs to at least one of these classes, we conclude that Mn is prime for every odd n such that 5≤ n≤ 2001. Finally, we conjecture that Mn is prime for all odd n≥ 5.

Published in American Journal of Mathematical and Computer Modelling (Volume 11, Issue 4)
DOI 10.11648/j.ajmcm.20261104.11
Page(s) 128-143
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2026. Published by Science Publishing Group

Keywords

Prime Labeling, Coprime, Prime Graph, Mobius Ladder

References
[1] A. Tout, A. N. Dabboucy and K. Howalla, Prime labeling of graphs, Nat. Acad. Sci. Letters, 11(1982) 365-368.
[2] H. L. Fu and K. C. Huang, On Prime labellings, Discrete Math. 127(1994), 181-186.
[3] J. A. Gallian, A Survey: A dynamic survey of graph labeling, Electron. J. Combin. 14(2007), 115-121.
[4] K. Carlson, Generalized books and Cm-snakes are prime graphs, Ars Combinatoria 80(2006), 215-221.
[5] Kh. Md. Mominul Haque,Lin Xiaohui, Yang Yuansheng and Zhao Pingzhong, On the prime labeling of generalized Petersen graph P(n, 1), Utilitas Mathematica 83(2010)95-106.
[6] Kh. Md. Mominul Haque,Lin Xiaohui, Yang Yuansheng and Zhao Pingzhong, Prime labeling on Kondel graphs W3,n, ARS Combinatoria 109 (2013), 113-128.
[7] Kh. Md. Mominul Haque,Lin Xiaohui, Yang Yuansheng and Zhao Pingzhong, On the Prime Labeling of Generalized Petersen Graphs P(n,3), Int. J. Contemp. Math. Sciences Vol. 6, 2011, no. 36, 1783-1800.
[8] M. A. Seoud, A. T Diab and E. A. Elsahowi, On strongly-C harmonious, relatively prime, odd graceful and cordial graphs, Proc. Math. Phys. Soc. Egypt, No. 73(1998), 33-55.
[9] M. A. Seoud and M. Z. Youssef, On prime labelings of graphs, Congr. Numer.141 (1999) 203-215.
[10] M.Sundaram, R. Ponraj and S. Somasundaram, On a Prime Labeling Conjecture, ARS Combinatoria. 79(2006), 205-209.
[11] O. Pikhurko, Every Tree with at most 34 vertices is prime, Utilitas Mathematica 62(2002), 185-190.
[12] O. Pikhurko, Trees are almost Prime, Discrete Mathematics 307(2007), 1455-1462.
[13] U. M. Prajapati and S. J. Gajjar, Some Results on Prime Labeling Open Journal of Discrete Mathematics 2014, 4, 60-66
[14] V. Vilfred, S. Somasundaram and T. Nicholas, Classes of prime graphs, International J. Management and Systems, to appear.
Cite This Article
  • APA Style

    Haque, K. M. M., Khanam, U. N., Shahriar, K. M. F. (2026). Prime Labeling of Mobius Ladder Graphs Mn. American Journal of Mathematical and Computer Modelling, 11(4), 128-143. https://doi.org/10.11648/j.ajmcm.20261104.11

    Copy | Download

    ACS Style

    Haque, K. M. M.; Khanam, U. N.; Shahriar, K. M. F. Prime Labeling of Mobius Ladder Graphs Mn. Am. J. Math. Comput. Model. 2026, 11(4), 128-143. doi: 10.11648/j.ajmcm.20261104.11

    Copy | Download

    AMA Style

    Haque KMM, Khanam UN, Shahriar KMF. Prime Labeling of Mobius Ladder Graphs Mn. Am J Math Comput Model. 2026;11(4):128-143. doi: 10.11648/j.ajmcm.20261104.11

    Copy | Download

  • @article{10.11648/j.ajmcm.20261104.11,
      author = {Khandoker Mohammed Mominul Haque and Umme Nasreen Khanam and Khandoker Mohammed Faiyaz Shahriar},
      title = {Prime Labeling of Mobius Ladder Graphs Mn},
      journal = {American Journal of Mathematical and Computer Modelling},
      volume = {11},
      number = {4},
      pages = {128-143},
      doi = {10.11648/j.ajmcm.20261104.11},
      url = {https://doi.org/10.11648/j.ajmcm.20261104.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20261104.11},
      abstract = {Graph labeling, in which integers are assigned to the vertices or edges of a graph subject to given conditions, is an active area of graph theory, and prime labeling is one of its well-studied variants. Let G=(V,E) be a graph with vertex set V and edge set E. A graph G is said to have a prime labeling if its vertices can be labeled with distinct integers from 1,2,…,|V| such that for every edge xy in G, the labels assigned to x and y are relatively prime or coprime. A graph is called prime if it has a prime labeling. The Mobius ladder Mn is the graph on 2n vertices (n≥ 3) formed by two paths v0,v1,…,vn-1 and u0,u1,…,un-1, the n rungs viui, and the two crossing edges un-1v0 and vn-1u0. Seoud and Youssef proved that Mn is not prime for even n. In this paper, we study the prime labeling of the Mobius ladder Mn for odd n. We first show that M3 is not prime. We then define explicit labeling functions for sixteen classes of odd n and prove that each function is a prime labeling by means of simple sufficient conditions for two labels to be coprime, for example that one label equals 1, that their sum is prime, or that their difference is 1 or a suitable prime power. Examples of the resulting labelings are illustrated in figures. Since every odd n with 5≤ n≤ 2001 belongs to at least one of these classes, we conclude that Mn is prime for every odd n such that 5≤ n≤ 2001. Finally, we conjecture that Mn is prime for all odd n≥ 5.},
     year = {2026}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Prime Labeling of Mobius Ladder Graphs Mn
    AU  - Khandoker Mohammed Mominul Haque
    AU  - Umme Nasreen Khanam
    AU  - Khandoker Mohammed Faiyaz Shahriar
    Y1  - 2026/11/18
    PY  - 2026
    N1  - https://doi.org/10.11648/j.ajmcm.20261104.11
    DO  - 10.11648/j.ajmcm.20261104.11
    T2  - American Journal of Mathematical and Computer Modelling
    JF  - American Journal of Mathematical and Computer Modelling
    JO  - American Journal of Mathematical and Computer Modelling
    SP  - 128
    EP  - 143
    PB  - Science Publishing Group
    SN  - 2578-8280
    UR  - https://doi.org/10.11648/j.ajmcm.20261104.11
    AB  - Graph labeling, in which integers are assigned to the vertices or edges of a graph subject to given conditions, is an active area of graph theory, and prime labeling is one of its well-studied variants. Let G=(V,E) be a graph with vertex set V and edge set E. A graph G is said to have a prime labeling if its vertices can be labeled with distinct integers from 1,2,…,|V| such that for every edge xy in G, the labels assigned to x and y are relatively prime or coprime. A graph is called prime if it has a prime labeling. The Mobius ladder Mn is the graph on 2n vertices (n≥ 3) formed by two paths v0,v1,…,vn-1 and u0,u1,…,un-1, the n rungs viui, and the two crossing edges un-1v0 and vn-1u0. Seoud and Youssef proved that Mn is not prime for even n. In this paper, we study the prime labeling of the Mobius ladder Mn for odd n. We first show that M3 is not prime. We then define explicit labeling functions for sixteen classes of odd n and prove that each function is a prime labeling by means of simple sufficient conditions for two labels to be coprime, for example that one label equals 1, that their sum is prime, or that their difference is 1 or a suitable prime power. Examples of the resulting labelings are illustrated in figures. Since every odd n with 5≤ n≤ 2001 belongs to at least one of these classes, we conclude that Mn is prime for every odd n such that 5≤ n≤ 2001. Finally, we conjecture that Mn is prime for all odd n≥ 5.
    VL  - 11
    IS  - 4
    ER  - 

    Copy | Download

Author Information
  • Department of Computer Science and Engineering, Shahjalal University of Science and Technology, Sylhet, Bangladesh

  • Department of Computer Science, Jayntapur Tayob Ali Technical College, Sylhet, Bangladesh

  • Department of Computer Science and Engineering, North South University, Dhaka, Bangladesh

  • Sections