Prime and Odd Prime Labelings on Cycle-Related Graphs - Komarullah, Hafif; Hidayat, Noor; Krisnawati, Vira Hari; Wijaya, Kristiana (Science and Technology Indonesia, 2026)
Graph labeling is the process of determining integer values for vertices, edges, or both, based on certain criteria. Let G be a simple graph with the finite vertex set V(G). Prime labeling of G is a bijection ⍺:V(G)→{1,2,…,|V(G)|} for which each pair of adjacent vertices exhibits relatively prime labels. This concept has been extended to odd prime labeling, defined as a bijection ⍺:V(G)→ {1,3,...,2|V(G)|-1} satisfying the condition that the labels assigned to adjacent vertices are relatively prime labels. A graph that displays a (odd) prime labeling is designated as a (odd) prime graph. A recent conjecture state that every prime graph is an odd prime graph. In the present study, we conduct an investigation concerning prime and odd prime labeling, focusing on a range of cycle-related graphs classes. Our methods include the axiomatic descriptive approach and pattern detection techniques. We show that volcano graphs, C_3 ⨀_(x_1 y_0 ) F_n, C_3⊚K ̅_n, tadpole graphs, palm trees, and C_l ⨀_(x_1 y_0 ) mP_(n+1) are all both prime and odd prime graphs.