This article studies edge irregular \((k)\)-labelings of complete graphs \((K_n)\) and aims to improve the existing upper bound for the edge irregularity strength \((es(K_n))\) through an algorithmic approach. The improvement is achieved using the branch and bound algorithm design strategy, whose selection is important because of the problem structure, computational complexity, possible serial or parallel execution, and accuracy requirements. Labeling complete graphs is difficult because the number of edges grows rapidly and many triangles are involved, making it challenging to maintain unique edge weights while searching for optimal labels. Since complete graphs serve as supergraphs for many graph families, results on them are particularly valuable. In 2018, Asim et al. proposed an algorithmic solution for complete graphs and gave the upper bound \((es(K_n)\leq E\log_2 |V|)\). This article uses the branch and bound strategy to address edge deficiency and improve that bound. Computational experiments are conducted for higher-order graphs, where the algorithm recursively generates constrained combinatorial structures to ensure unique edge weights. The results show that the proposed branch and bound algorithm significantly improves the upper bound for \((es(K_n))\) compared with previous results.
Algorithm design and optimization play an important role in increasing computational efficiency, reducing processing cost and uses memory efficiently. Optimization consists of tweaking algorithm design strategies to improve performance, reduce computational complexity, and ensure scalability. By proper use of these strategies, we can achieve significant improvements in different types of applications, from data processing to problem-solving in diverse fields.
Graph labeling is a critical area of study in computer science and mathematics by focusing on assigning integer number to the edges or vertices or both of a graph according to certain rules. Consider \(G\) is a simple, undirected graph consists of a vertex set, \(V(G)\), and an edge set, \(E(G)\). When referring to labeling, we denote any mapping that assigns a set of integer numbers, known as labels, to the vertices or edges of the graph. Over the past decades, interest in graph labeling has grown substantially, with more than 200 labeling methods introduced and over 3000 research works published in the field [19].
Chartrand et al. [15] introduced the concept of edge \(k\)-labeling \(\delta\) of a graph \(G\) such that \(w_{\delta}(x) \neq w_{\delta}(y)\) for all distinct vertices \(x, y \in V(G)\). Such a labeling is called an irregular assignment, and the irregularity strength \(s(G)\) of a graph \(G\) is defined as the smallest \(k\) for which \(G\) admits an irregular labeling using labels from \(\{1,2,\ldots,k\}\). This parameter has garnered significant attention in articles [7, 8, 14, 17, 18].
Bača et al. [13] explored two modifications of the irregularity strength of graphs, specifically a total edge irregularity strength, denoted by \(tes(G)\), and a total vertex irregularity strength, denoted by \(tvs(G)\). Some results regarding total edge irregularity strength and total vertex irregularity strength can be found in the articles [3, 5, 4, 20, 21, 24, 26].
In 2014, Ahmad et al.[6] introduced an edge irregular \(k\)-labeling and established a lower bound for this type of labeling. A vertex \(k\)-labeling \(V(G) \to \{1,2,3,\ldots,k\}\) ensures that for any two distinct edges \(e\) and \(f\), their respective weights \(w_{\phi}(e)\) and \(w_{\phi}(f)\) are different. Here, the weight of an edge \(e = xy \in E(G)\) is calculated as \(w_{\phi}(xy) = \phi(x) + \phi(y)\). In this case, the weight of an edge is defined as the sum of the labels of its ends. The minimum \(k\) for which a graph \(G\) has an irregular \(k\)-labeling is called the edge irregularity strength of \(G\), denoted by \(es(G)\). In recent years, a lot of work has been done on \(es(G)\) for different families of graphs and trees using mathematically and algorithmically [2, 10, 11, 12, 23, 27, 28, 30, 29].
Theorem 1.1([6]).Let \(G=(V,E)\) be a simple graph with maximum degree \(\Delta = \Delta(G)\). Then \[es(G) \geq \max\left\{ \left\lceil\frac{|E(G)|+1}{2}\right\rceil, \Delta(G) \right\}.\]
Edge irregular \(k\)-labeling is a significant area of study in graph theory due to its applications in network design, resource distribution, and information encoding, where computing unique weights to edges can help prevent ambiguity and conflicts. Among various graph types, complete graphs \(K_n\) present a particularly challenging case because of the highest number of edges \(\left(\frac{n(n-1)}{2}\right)\), leading to a combinatorially complex labeling space.
Asim et al. [9] as first attempt have computed the edge irregular \(k\)-labeling using an algorithmic approach satisfying Theorem 1. Their contribution established an upper bound for the edge irregularity strength of complete graphs and laid a foundation for further algorithmic investigation. However, as the graph size increases, the difficulty of ensuring unique edge weights through vertex labeling grows exponentially, and several edge deficiencies remain in the computed results.
While they have explored the edge irregular \(k\)-labeling of complete graphs \(K_n\), but their findings have uncovered several edge deficiencies that needs attention and improvement through various design strategies. By addressing these deficiencies,it is possible to reducing the minimum of the maximum lable \(k\), which directly translates to optimizing the use of labels and improving algorithmic efficiency. These shortcomings could be mitigated by employing optimization techniques, algorithmic modifications, or restructuring the computation process. However, it is important to note that the algorithms presented in [9] computes the edge irregular \(k\)-labeling using decrease and conquer strategy bearing the time complexity as \(O(|V|) \leq |V|^2\).
In this paper, our primary objective is to improve the mathematical results on edge irregular \(k\)-labeling and remove edge deficiencies in complete graphs \(K_n\) by leveraging a branch and bound algorithm design strategy [9]. The algorithm is intentionally designed to eliminate edge deficiencies, prioritizing labeling accuracy over time complexity. In other words, the focus is placed on finding edge irregular \(k\)-labelings with smaller maximum labels that is, improved values or bounds for \(es(K_n)\), even if this requires additional computational resources [1]. Unlike sequential execution, which processes one labeling branch at a time, the parallel version distributes multiple labeling paths across CPU cores to explore the search space concurrently [16]. This design choice enables the algorithm to remain computationally feasible for larger values of \(|V|\), while still addressing the limitations of prior single-core approaches. Although this parallel strategy increases implementation complexity, it significantly improves runtime performance without compromising the algorithm’s primary goal—reducing the maximum label used in an edge irregular \(k\)-labeling.
This section is used to work on a parallel algorithmic framework for computing edge-irregular \(k\)-labelings of complete graphs \(K_n\). The purpose is to reduce the edge deficiencies by ensuring that every edge weight is unique and at the same time, the main goal is to minimize the maximum assigned label. A non recursive branch-and-bound approach is used to explore feasible labeling configurations and discard the invalid or suboptimal paths efficiently. To improve scalability, the algorithm implements parallel processing, enabling concurrent traversal of the exponential search space and significantly reducing computation time.
The algorithm follows a stack-based depth-first search strategy, distributed across multiple cores. It starts with a fixed seed of initial labels \([1,2,3,5]\), and the total number of edges \(E = \frac{|V|(|V|-1)}{2}\) is used to estimate an upper bound on label values. Each parallel worker explores a disjoint section of the search space, evaluating label combinations and verifying edge weight uniqueness via a hash set. Valid extensions are pushed back onto the stack for further exploration. Shared data structures are used to coordinate the best result across processes.
Combination (combo): contains the current sequence of vertex labels used in the graph.
Edge Set (edge_set): is used to store the existing edge weights and it must keep all edge weight unique.
Stack (stack): Used for non-recursive DFS to manage the state of the combination.
Shared Best (shared_best): A synchronized dictionary is used to track the global best labeling across all threads.
Lock (lock): Ensures safe access to shared data during concurrent updates.
Worker Arguments (args):is used to contains input configurations for each parallel worker.
To improve efficiency and scalability, several optimization strategies are integrated:
Pruned Depth-First Exploration: DFS explores different branches to achieve the target combination of labeling but infeasible branches are discarded early through branch-and-bound pruning to limit exponential expansion.
Hash-Based Edge Validation: Dynamic hash sets are used to check the uniqueness of new edge with near-constant-time.
Golden-Ratio Spacing Heuristic: Label growth and gap within consecutive label is controlled using a geometric spacing rule derived from the golden ratio [25].
Early Termination Threshold: Any branch where the next label exceeds twice the previous label is immediately terminated.
Redundancy-Aware Computation: Intermediate edge-states are reused to avoid recalculation of the labels.
Stack-Based Memory Optimization: Iterative DFS replaces recursion, lowering overhead for large values of \(|V|\).
Parallel Search Synchronization: In parallel processing multiple workers share and update a global best bound to ensure consistent pruning across threads.
The parallel processing algorithm is used to maintain computational feasibility for large and complex graphs. Independent labeling paths are distributed across multiple CPU cores, with each core maintaining its own edge state and exploring the search space from a distinct initial label. A shared global tracker records and updates the best solution found across all workers, ensuring correctness while efficiently coordinating progress. This type of design enables the method to remain tractable even for large and complex graphs, where sequential exploration would become prohibitively expensive [16, 22].
This section presents some examples as pilot testing to compare the significant improvements of this work with previously known results. A new algorithm is designed using a branch and bound strategy, and the results are verified by implementing the algorithms using the computer programming language. The success of the new strategy is based on addressing edge deficiencies.
The presented algorithm is a combination generator with specific constraints to avoid edge duplication. Once a combination is formed, it records the value of \(k\) and then systematically explores other combinations for further improvements, as shown in Figures 1 and 2.
Figure 1 displays the vertex label combinations generated for \(|V| = 11\). Five distinct combinations were obtained: \[\begin{gathered} \{1,2,3,5,8,13,21,30,39,53,74\},\\ \{1,2,3,5,8,13,21,30,39,54,69\},\\ \{1,2,3,5,8,14,23,33,41,49,65\},\\ \{1,2,3,5,8,14,25,35,45,53,61\},\\ \{1,2,3,5,9,16,29,38,50,55,60\}. \end{gathered}\]
Each combination yields an edge irregular \(k\)-labeling of \(K_{11}\), producing maximum label values 74, 69, 65, 61, and 60, respectively. Since 60 is the smallest among them, we conclude that an improved upper bound on \(es(K_{11})\) is 60, confirming an improvement over previously reported results. The weight of each edge is obtained by summing the labels corresponding to the row and column entries. In constructing the edge-weight matrix, the column index \(c\) is considered only when \(c > r\) and \(c \leq |V|\), ensuring that each pair is counted once and no duplicate edge weights arise.
By using this approach, an edge label deficiency can be reduced identified in previously published work. Through systematic exploration and adherence to strict constraints, our algorithm offers a robust solution for improving the edge irregular \(k\)-labeling of complete graphs \(K_n\), providing valuable insights for advancing graph theory and computational methodologies.
In terms of data structure and memory space point of view, the proposed algorithm optimally utilizes hash sets and combination generators to ensure efficient storage and retrieval of vertex labels. By leveraging hash sets, the algorithm minimizes redundant calculations and prevents duplicate edge weights, leading to a reduction in memory overhead. Additionally, the branch and bound approach strategically prunes infeasible solutions, significantly reducing the search space and improving computational efficiency. These enhancements contribute to a scalable and memory-efficient solution for computing edge irregular \(k\)-labeling of complete graphs.
Figure 2 presents the computed edge irregular \(k\)-labelings for \(|V| = 20\). In previously published work, the edge irregularity strength of \(K_{20}\) was given as \(es(K_{20}) = 413\). Using our branch and bound approach, multiple valid \(k\)-labelings were generated and the maximum label in each case was recorded. Among these, the smallest value obtained was 284, thereby establishing that an improved upper bound on \(es(K_{20})\) is 284. This demonstrates a significant improvement over the earlier reported value, validating the effectiveness of the proposed computational strategy.
Algorithm 1 explores valid vertex labelings using an iterative, stack-based depth-first search. Starting from a partial labeling, it extends the combination by appending new labels while ensuring that all resulting edge weights remain distinct. Labelings that exceed structural constraints or duplicate edge weights are pruned early. Upon reaching a complete labeling of size \(|V|\), the algorithm updates the global best solution if a smaller maximum label is achieved, ensuring thread-safe access to shared data structures.
Algorithm 3 constructs valid vertex labelings by iteratively extending a partial vertex labeling \(f : V(K_n) \to \mathbb{Z}^{+}\), starting from a given index. At each step, a candidate label is appended, and the uniqueness of all induced edge weights \(w(uv) = f(u)+f(v)\) is verified. If the labeling remains feasible, the process continues recursively. Upon reaching a complete labeling of size \(|V|\), the algorithm returns the maximum assigned label. If this value is smaller than the current upper bound of the edge irregularity strength \(es(K_n)\), it updates the bound accordingly. The search explores all label extensions within a bounded domain while pruning infeasible paths.
Algorithm 4 verifies the uniqueness of newly formed edge weights resulting from extending a partial vertex labeling \(f : V(K_n) \to \mathbb{Z}^{+}\). It constructs the set of all previously generated edge weights and checks whether any new edge weight of the form \(w(uv) = f(u)+f(v)\), where \(u\) is the newly added vertex and \(v\) is an existing vertex, already exists. If duplication is detected, the algorithm terminates early. Otherwise, it returns the list of newly generated unique edge weights. The verification process operates in \(O(|V|)\) time, improving efficiency during incremental label extension.
A computer program has been developed to test the algorithm under discussion and compute the results for various input values of vertices \(|V|\) of the complete graph \(K_n\).
The comparison of branch and bound and iterative approach while labeling the vertices is presented in Table 1.
The proposed algorithm was tested up to \(|V| = 50\) due to the exponential increase in computational complexity and memory requirements as the graph size grows. For instance, even a relatively small instance such as \(|V| = 5\), when selecting labels from the set \(\{1,2,\ldots,8\}\), requires evaluating \(P(8,5) = 6,720\) unique permutations. Each permutation involves checking \(\frac{|V|(|V|-1)}{2}\) edge weights to ensure all are unique—a process that becomes increasingly exhaustive as \(|V|\) increases.
To address this challenge, our branch and bound (B&B) strategy initiates the labeling process with a fixed seed combination \(\{1,2,3,5\}\). The next (fifth) element is generated starting from 6 onwards, and subsequent elements are incrementally determined based on the previous value. Importantly, the gap between consecutive elements is restricted to no more than 1.6 times the value of the preceding element. This constraint aligns with the golden ratio, serving as a termination condition to optimize the search space and improve efficiency.
During execution, the algorithm records the last successful labels of the current combination. It then backtracks to explore other possible combinations starting from that point. If a newly generated combination yields a lower final value (the corresponding value of \(k\)) than any previously recorded, it is retained as the current best solution. This recursive exploration continues until all valid combinations have been tested, and the labeling configuration with the smallest maximum label is identified for the edge irregularity strength of the given complete graph.
| Input List | Calculated Values | |||
|---|---|---|---|---|
| —V— | E | Branch & Bound | Iterative | \(\left\lfloor E\log_2 |V|\right\rfloor\) |
| 5 | 10 | 8 | 8 | 23 |
| 6 | 15 | 13 | 13 | 38 |
| 7 | 21 | 19 | 21 | 58 |
| 8 | 28 | 25 | 30 | 84 |
| 9 | 36 | 35 | 39 | 114 |
| 10 | 45 | 47 | 53 | 149 |
| 11 | 55 | 60 | 74 | 190 |
| 12 | 66 | 74 | 95 | 236 |
| 13 | 78 | 91 | 128 | 288 |
| 14 | 91 | 108 | 152 | 346 |
| 15 | 105 | 132 | 182 | 410 |
| 20 | 190 | 284 | 413 | 821 |
| 25 | 300 | 595 | 717 | 1393 |
| 30 | 435 | 977 | 1161 | 2134 |
| 35 | 595 | 1501 | 1722 | 3051 |
| 40 | 780 | 2154 | 2497 | 4151 |
| 45 | 990 | 2961 | 3332 | 5436 |
| 50 | 1225 | 3914 | 4447 | 6913 |
In Figure 3, the chart shows the differences between the branch and bound approach and the iterative approach, as well as the calculated results in relation to \(es(K_n) \leq E\log_2 |V|\), we can observe the following:
1. Branch and Bound Approach vs. Iterative Approach in \(K_n\): The branch and bound approach tends to yield lower values compared to the iterative approach for \(es(K_n)\) across various values of \(|V|\) and \(E\). This suggests that the branch and bound approach is more effective at finding labelings whose maximum label (and thus the computed value of \(es(K_n)\)) is smaller than that obtained by the iterative approach. The iterative approach produces higher values for \(es(K_n)\), indicating that it may not be as effective in reducing edge irregularity or optimizing graph labeling compared to branch and bound.
2. Comparison with Theoretical Bound \(es(K_n) \leq E\log_2 |V|\): – The calculated \(es(K_n)\) values from both approaches are compared against the theoretical upper bound given by \(E\log_2 |V|\). – In most cases, the calculated \(es(K_n)\) values are within reasonable proximity to the theoretical bound, indicating that the graph labeling algorithms are performing relatively well.
Overall, the comparison highlights the effectiveness of the branch and bound approach in producing smaller computed values of \(es(K_n)\) compared to the iterative approach. Additionally, the analysis against the theoretical bound provides insights into the performance of the graph labeling algorithms in relation to established theoretical limits.
The time complexity of an algorithm shows the effectiveness and scalability of the proposed algorithm. The primary goal of this section is to quantify the computational cost associated with each function used in the edge irregular labeling process. Since the overall algorithm employs recursive, combinatorial search strategies with parallel processing enhancements, it is very important to compute the time complexity of each function step by step. We analyze each function individually IsUnique, CombGenerator, Worker, and Complete-Graph-Labeling to determine their theoretical worst-case complexity in terms of the number of vertices \(|V|\) and edges \(E = \frac{|V|(|V|-1)}{2}\). This breakdown enables us to estimate the total computational load and justify the use of parallelization for handling larger graph sizes.
The function IsUnique verifies whether adding a new vertex label preserves the uniqueness of all induced edge weights. In the proposed implementation, the edge weights are conceptually treated as a flattened hash set for efficient membership testing. However, in the provided pseudocode implementation, the edge weights are dynamically flattened from hash_set into a temporary set during each function call.
When a new label is considered, the algorithm checks the sums between the new label and each existing vertex label.
Since the combination contains at most \(|V|\) labels, and each membership test in the hash set is performed in constant time, the overall time complexity of IsUnique is \[O(|V|).\]
This optimized design avoids iterating over all edges and ensures that the complexity of IsUnique does not depend on the number of edges \(E\).
The CombGenerator function incrementally extends a partial labeling by assigning new vertex labels while maintaining the uniqueness of edge weights. Initially, four labels are fixed, reducing the number of labels to be assigned to \(|V|-4\), where \(|V|\) is the number of vertices. The available label pool is of size \(O(|V|^2\log |V|)\), based on the estimated upper bound for the maximum label value.
At each recursion level, the function loops over up to \(O(|V|^2\log |V|)\) candidate labels. Each candidate requires a validation step using the optimized IsUnique function, which operates in \(O(|V|)\) time. Consequently, the cost per level is: \[O(|V|^3\log |V|).\]
Since the recursion depth can reach up to \(|V|-4\) levels, the total number of explored combinations follows an exponential growth with respect to \(|V|\). Thus, the worst-case total time complexity of CombGenerator is: \[O\left((|V|^2\log |V|)^{|V|} \times |V|\right).\]
The DFS-Worker algorithm implements a stack-based depth-first search to generate edge irregular \(k\)-labelings. It explores different combinations of vertex labels iteratively by:
Maintaining a stack of partial labelings.
Extending partial labelings by attempting to add new labels from the candidate range.
Validating the uniqueness of edge weights for each extension using the IsUnique function.
At each node (i.e., each partial labeling), the following operations occur:
Checking if the current combination is complete (\(O(1)\)).
Finding the maximum label (\(O(1)\)), updating the shared best (\(O(1)\)).
Iterating over candidate labels (up to \(O(|V|^2\log |V|)\) candidates).
For each extension, calling IsUnique which runs in \(O(|V|)\) time.
The total number of nodes (i.e., partial labelings) that may be generated is asymptotically bounded by the number of ways to assign \(|V|-4\) labels: \[O\left((|V|^2\log |V|)^{|V|}\right).\]
Thus, multiplying the cost per node by the number of nodes, the overall time complexity of DFS-Worker is: \[O\left((|V|^2\log |V|)^{|V|} \times |V|\right).\]
The Complete-Graph-Labeling algorithm serves as the main driver function, orchestrating the parallel search for an optimal edge irregular \(k\)-labeling for complete graphs \(K_n\). Its key steps involve:
Calculating the number of edges \(E = \frac{|V|(|V|-1)}{2}\) and the upper bound for labels \(Last = E \times \lfloor\log_2 |V|\rfloor\).
Generating a range of candidate label values, of size approximately \(O(|V|^2\log |V|)\).
Dividing the candidate label range into chunks and distributing them across multiple processors.
For each candidate, a parallel worker process attempts to construct a valid labeling.
Each call to a Worker executes a DFS-Worker routine, whose time complexity has been established as: \[O\left((|V|^2\log |V|)^{|V|} \times |V|\right).\]
The number of parallel tasks submitted is proportional to the number of candidate starting values, that is \(O(|V|^2\log |V|)\). However, since the search is distributed across \(P\) processors, the total effective time complexity is reduced by a factor of \(P\).
Thus, the overall time complexity of Complete-Graph-Labeling becomes: \[O\left(\frac{(|V|^2\log |V|)^{|V|} \times |V|}{P}\right),\] where \(P\) is the number of available parallel processing units.
The proposed framework for computing edge irregular \(k\)-labeling of complete graphs integrates four core algorithms: IsUnique, CombGenerator, DFS-Worker, and Complete-Graph-Labeling.
The IsUnique function operates in \(O(|V|)\) time due to the flattened hash set.
The CombGenerator function recursively explores valid labelings over a candidate label range of order \(O(|V|^2\log |V|)\). In the worst case, it evaluates many such candidates at each recursion level and invokes IsUnique for each, leading to an exponential-time behaviour dominated by a factor of \((|V|^2\log |V|)^{|V|}\), multiplied by a polynomial overhead in \(|V|\) and \(E\).
The DFS-Worker algorithm mirrors the search space of CombGenerator, but uses an explicit stack-based depth-first strategy while repeatedly calling IsUnique to prune infeasible labelings.
The Complete-Graph-Labeling function coordinates the parallel execution by distributing disjoint portions of the search space across \(P\) processing units and aggregating the best solution found.
Considering the exponential nature of the solution space and the use of parallelism, a worst-case upper bound on the overall time complexity of the complete framework can be expressed as \[{O\left(\frac{(|V|^2\log |V|)^{|V|}\cdot (|V|)}{P}\right)}, \tag{1}\] where
\(|V|\) is the number of vertices,
\(P\) denotes the number of parallel processing units.
This research presents a comprehensive investigation into the edge irregular \(k\)-labeling of complete graphs \(K_n\), focusing on addressing previously observed edge deficiencies and enhancing the mathematical precision of labeling strategies. Through the development of a novel branch-and-bound algorithmic framework, we have achieved a notable improvement in the upper bound of edge irregularity strength. Specifically, the proposed method suggests a better upper bound than was previously proposed from \(E\log |V|\) to a more efficient expression \(E\log\left(\frac{|V|}{2}\right)\), representing a significant advancement in the labeling methodology for complete graphs.
The mathematical refinement achieved in this work can be summarized by the following relation: \[{E\cdot \log_2\left(\frac{|V|}{2}\right) < E\cdot \log_2 |V| < F_n}. \tag{2}\]
The proposed approach consistently produces tighter upper bounds for the edge irregularity strength \(es(K_n)\) as the graph size \(|V|\) increases. This result shows the effectiveness of the algorithm to reduce duplicate edge weights and eliminate edge deficiencies, outperforming conventional iterative methods. The close alignment between empirical outcomes and theoretical predictions shows the mathematical soundness and robustness of the proposed solution.
A good contribution of this work is the integration of parallel processing to mitigate the exponential computational complexity inherent in recursive labeling algorithms. By distributing the search space across \(P\) processing units, the effective runtime is reduced from \(O(|V|^2\log |V|)^{|V|}\times |V|\) to: \[{O\left(\frac{(|V|^2\log |V|)^{|V|} \times |V|}{P}\right)},\] thereby ensuring scalability without compromising the correctness or precision of the labeling process. A future research work include extending this algorithmic framework to different classes of graphs which includes the circulant graphs, bipartite graphs, and strong product graphs, to evaluate its adaptability and generalization capabilities. Further enhancements may incorporate dynamic pruning strategies, heuristic-driven labeling methods, and GPU-accelerated parallelism to efficiently address increasingly complex graph instances.
Overall, this research contributes a mathematically rigorous and computationally scalable solution to the edge irregular \(k\)-labeling problem. It provides both theoretical insights and practical methodologies, establishing a foundation for future advances in graph labeling, combinatorial optimization, and high-performance algorithm design.