On Prime and Coprime Edge Labeling of Some Graphs - Hafif Komarullah; Kristiana Wijaya; Vira Hari Krisnawati; Noor Hidayat (Jurnal Matematika UNAND, 2026)
A coprime edge labeling of a graph is defined as a labeling in which positive integer labels are assigned to each edge of the graph according to certain rules. In this labeling, every pair of edges adjacent to the same vertex must have relatively prime labels, meaning they have no common factors other than one. If the number of labels used is equal to the total number of edges of the graph, this labeling method is designated as a prime edge labeling. In the context of coprime edge labeling, the smallest possible number of labels that allows such a labeling is referred to as the minimum coprime edge number. The present study analyzes prime edge labeling and coprime edge labeling on several special graphs, including tadpoles, combs, disjoint unions of combs, unions of two cycles, disjoint unions of paths, volcano graphs, and regular caterpillars. Furthermore, this study provides precise values for the minimum coprime edge number of the Cn \cup Cm graphs with odd n and m, volcano graphs, and regular caterpillars.