تقریب عدد موقعیت عمومی یالی گراف‌ها با استفاده از الگوریتم‌های فراابتکاری

نویسندگان
فریدون رهبرنیا
زهرا حامدلبافیان
دانشگاه فردوسی مشهد
چکیده
یک زیرمجموعه از یال‌های گراف، مجموعه موقعیت عمومی یالی نامیده می‌شود اگر برای هر جفت یال در آن، تمامی کوتاه‌ترین مسیرهای بین آن‌ها شامل هیچ یک از یال‌های زیرمجموعه نباشد. هدف اصلی این پژوهش، تقریب عدد موقعیت عممومی یالی گراف‌ها با بهره‌گیری از الگوریتم‌های فراابتکاری، شامل الگوریتم ژنتیک و تبرید شبیه‌سازی شده، می‌باشد.
کلیدواژه‌ها
گراف
مجموعه موقعیت عمومی یالی
الگوریتم تبرید شبیه‌سازی‌شده
الگوریتم ژنتیک

عنوان مقاله English

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

نویسندگان English

Freydoon Rahbarnia
Zahra Hamedlabbafian
Ferdowsi uniwersity of mashhad
چکیده English

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.

کلیدواژه‌ها English

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.