EUVIMEDEUVIMED entdecken
Crossref

A branch and bound algorithm for improving the Upper Bound on the edge irregularity strength of complete graph

Muhammad Shahzad, Muhammad Ahsan Asim, Roslan Hasni, Ali Ahmad

Ars Combinatoria · 17.06.2026 · 167 · 195-221

DOI: 10.61091/ars167-13 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Ars Combinatoria, online erschienen am 17.06.2026. Verfasst von Muhammad Shahzad und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Shahzad, M., Asim, M. A., Hasni, R., & Ahmad, A. (2026). A branch and bound algorithm for improving the Upper Bound on the edge irregularity strength of complete graph. Ars Combinatoria, 167, 195-221. https://doi.org/10.61091/ars167-13

Vancouver

Shahzad M, Asim MA, Hasni R, Ahmad A. A branch and bound algorithm for improving the Upper Bound on the edge irregularity strength of complete graph. Ars Combinatoria. 2026;167:195-221. doi:10.61091/ars167-13

BibTeX
@article{Shahzad2026,
  author = {Shahzad, Muhammad and Asim, Muhammad Ahsan and Hasni, Roslan and Ahmad, Ali},
  title = {A branch and bound algorithm for improving the Upper Bound on the edge irregularity strength of complete graph},
  journal = {Ars Combinatoria},
  year = {2026},
  volume = {167},
  pages = {195--221},
  doi = {10.61091/ars167-13}
}
Kostenlos starten →