An Investigation on the Edge-gracefulness of Bubble Sort, Bubble Sort Star, and Kulli-Cycle Windmill Graphs

Abstract

A fundamental area of graph theory, graph labeling concerns the assignment of integers to the vertices, edges, or both of a graph under specified constraints. One of the many types of graph labeling is edge-graceful labeling. Edge-graceful labeling requires assigning distinct integers from 1 to q to the edges of a graph G with p vertices and q edges so that the induced vertex labels, obtained by summing the labels of all incident edges modulo p, are pairwise distinct. Now, determining which graph families admit such labeling remains challenging, and this study focuses on the edge-gracefulness of bubble sort graphs, bubble sort star graphs, and Kulli-cycle windmill graphs, whose orders and sizes depend on multiple variables or factorial terms, unlike simpler graphs determined by a single parameter. Using the contrapositive of Lo’s Theorem and number-theoretic techniques, we establish that the bubble sort graph B_n is not edge-graceful whenever the parameter n is not an even integer that is greater than or equal to 4, that the only bubble sort star graphs that have the potential to be edge-graceful are BS_n with n ≥ 4, and that W₃ is the only edge-graceful Kulli-cycle windmill graph.