On Prime Labelings of Uniform Cycle Snake Graphs

  • Agam Bedi Emerson College
  • Matt Ollis Emerson College
  • Samiksha Ramesh Emerson College
Keywords: coprime integers; graph labeling; prime graph; snake graph

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 Cmk,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 Cmk,q for many pairs (k,q) and, in each case, all m. These include: all cases with ≤   9 or k = 11; all cases with q = 2 when k ≡ 3 (mod 4); all cases with q = 3 when k has the form 2a 1, 3a + 1 or 3b + 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).

Published
2023-04-18
How to Cite
Bedi, A., Ollis, M., & Ramesh, S. (2023). On Prime Labelings of Uniform Cycle Snake Graphs. The PUMP Journal of Undergraduate Research, 6, 151-171. https://doi.org/10.46787/pump.v6i0.3633