Explicit prime labelings for families of unicyclic graphs with star and path attachments

Abstract

A graph G admits a prime labeling if its vertices can be assigned the integers 1,2,. . . ,|V(G)| so that every pair of adjacent vertices receives coprime labels; a graph with this property is called a prime graph. This paper studies prime labeling for unicyclic graphs formed by attaching stars or pairs of pendant paths to every vertex of a cycle. Here C_n  * S_m denotes the graph obtained by attaching m new pendant vertices to each vertex of C_n. We give explicit constructions showing that C_n * S₂, C_n * S₄, and C_n * S₆ -- cycles with two, four, or six pendant vertices at each cycle vertex -- are all prime graphs, extending known results for three, five, and seven pendant vertices. We then consider unicyclic graphs in which every cycle vertex is identified with one endpoint of each of two paths P_k1 and P_k2, where k₁ ≥ k₂, and prove that such a graph is prime whenever gcd(k₁ - 1, k₂) = 1 and gcd(k₂, n - 1) = 1, or whenever gcd(k₁, k₂ - 1) = 1 and gcd(k₁, n - 1) = 1. A direct consequence is that a unicyclic graph whose two pendant paths both have k vertices is prime whenever gcd(k, n - 1) = 1. Worked examples accompany each construction, so the labelings are straightforward to verify and to extend to other unicyclic families.