On Prime Labelings of Uniform Cycle Snake Graphs

Abstract

A prime labeling of a graph of order n is an assignment of the integers 1, 2, ... , n to the vertices such that each pair of adjacent vertices has coprime labels. For positive integers m, k, q with k  ≥  3 and 1  ≤  q   ≤ ⌊k/2⌋ , the uniform cycle snake graph C^m_k,q is constructed by taking a path with m edges and replacing each edge by a k-cycle by identifying two vertices at distance q in the cycle with the vertices of the original path edge. We construct prime labelings for C^m_k,q for many pairs (k,q) and, in each case, all m. These include: all cases with k  ≤   9 or k = 11; all cases with q = 2 when k ≡ 3 (mod 4); all cases with q = 3 when k has the form 2^a − 1, 3^a + 1 or 3^b + 3 for all a and all odd b; all cases with q = 4 when k is even; and all cases with q = k/2 when q is a prime congruent to 1 (mod 3).