Research Article
Prime Labeling of Mobius Ladder Graphs Mn
Khandoker Mohammed Mominul Haque*
,
Umme Nasreen Khanam,
Khandoker Mohammed Faiyaz Shahriar
Issue:
Volume 11, Issue 4, December 2026
Pages:
128-143
Received:
16 April 2026
Accepted:
3 May 2026
Published:
18 November 2026
DOI:
10.11648/j.ajmcm.20261104.11
Downloads:
Views:
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.
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 in...
Show More