Scalable and Efficient Approaches to Graceful Labelling in Graph Theory

Graceful labelling is a fundamental problem in graph theory with significant applications in communication networks, coding theory, VLSI circuit design, and combinatorial optimization. The graceful tree conjecture, proposed by Rosa in 1967, asserts that every tree can be assigned a graceful labelling, yet a general proof or counterexample remains elusive. Traditional constructive techniques and exhaustive searches have established results for specific graph families, but scalability challenges persist when dealing with larger instances. This paper investigates scalable and efficient approaches to graceful labelling by integrating constructive methods with heuristic and optimization-based strategies. We explore hybrid approaches that combine deterministic recursive labelling with stochastic metaheuristics such as genetic algorithms, simulated annealing, and tabu search. Additionally, we examine the role of integer linear programming (ILP), constraint satisfaction formulations, and parallel algorithms leveraging GPU acceleration and distributed computing frameworks. Experimental evaluations demonstrate that hybrid and parallel approaches outperform traditional heuristics in terms of scalability and efficiency, particularly for large trees and special graph families. Approximation-based relaxations are also shown to provide near-graceful solutions that guide heuristic refinement. Beyond computational advancements, this work highlights theoretical implications, including potential structural insights into the graceful tree conjecture and extensions to cyclic graphs. The proposed scalable frameworks not only advance computational verification but also contribute to bridging the gap between practical applications and theoretical challenges in graph labelling.