On the Minimum Coprime Number of Some Graphs

Abstract

Let G be a finite simple graph. A coprime labeling of G is an injective assignment of positive integers to the vertices such that adjacent vertices receive relatively prime labels. The minimum coprime number of G, denoted by pr(G), is the smallest integer k for which G admits a coprime labeling using labels from {1, 2, ..., k}. In this paper, we determine the exact minimum coprime number of several graph families, namely the disjoint union of cycle graphs, the disjoint union of complete graphs, and dumbbell graphs. For the graph mCn with n odd, explicit coprime labeling constructions are provided and exact values of pr(mCn) are obtained for several infinite families. We also establish exact minimum coprime numbers for mKn and characterize prime and coprime labelings of dumbbell graphs according to the parity of their parameters. Furthermore, constructive labeling functions are presented for all considered graph classes. These results extend previous studies on minimum coprime labeling for graph operations and disconnected graph families.