Prime and odd prime labelings of several graph classes

Source 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 <em>K</em><sub>1,1,n </sub>⊙ 2<em>S</em><sub>m</sub> 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.