Approximating the edge general position number of graphs using meta-heuristic algorithms

Authors
Freydoon Rahbarnia
Zahra Hamedlabbafian
Ferdowsi uniwersity of mashhad
Abstract
A subset of a graph’s edges is called an edge general position set if, for every pair of edges in the subset, none of the shortest paths between them contain any edge from the subset.

The main objective of this study is to approximate the edge general position number of graphs using metaheuristic algorithms, including the Genetic Algorithm and Simulated Annealing.
Keywords
Graph
edge general position set
Simulated annealing algorithm
Genetic Algorithm
1. Ghorbani, M. (2013). Fullerene graphs with pentagons and heptagons. Journal of Discrete Mathematics and Its Applications, 3(1-2), 33-37.

2. Hamed-Labbafian, Z., Sabeghi, N., Tavakoli, M., & Klavžar, S. (2025). Three algorithmic approaches to the general position problem. Bulletin of the Australian Mathematical Society. DOI:10.1017/S0004972725100178.

3. Klavžar, S., & Tan, E. (2023). Edge general position sets in Fibonacci and Lucas cubes. Bulletin of the Malaysian Mathematical Sciences Society, 46(4), 120.

4. Korže, D., & Vesel, A. (2023). General position sets in two families of Cartesian product graphs. Mediterranean Journal of Mathematics, 20(4), 203.

5. Manuel, P., & Klavžar, S. (2018). A general position problem in graph theory. Bulletin of the Australian Mathematical Society, 98(2), 177-187.

6. Manuel, P., Prabha, R., & Klavžar, S. (2022). The edge general position problem. Bulletin of the Malaysian Mathematical Sciences Society, 45(6), 2997-3009.

7. Manuel, P., Prabha, R., & Klavzar, S. (2022). Generalization of edge general position problem. arXiv preprint arXiv:2207.07357.

8. Patkós, B. (2019). On the general position problem on Kneser graphs. arXiv preprint arXiv:1903.08056.

9. Tian, J., & Xu, K. (2021). The general position number of Cartesian products involving a factor with small diameter. Applied Mathematics and Computation, 403, 126206.

10. Tian, J., Xu, K., & Chao, D. (2023). On the general position numbers of maximal outerplane graphs. Bulletin of the Malaysian Mathematical Sciences Society, 46(6), 198.

11. Tian, J., Klavžar, S., & Tan, E. (2024). Extremal edge general position sets in some graphs. Graphs and combinatorics, 40(2), 40.

12. Parthasarathy, G. J. (2016). The geodesic irredundant sets in graphs. MATHEMATICAL COMBINATORICS (INTERNATIONAL BOOK SERIES), Vol. 4, 2016, 135.