ISSN 2590-9770
The Art of Discrete and Applied Mathematics 8 (2025) #P1.02
https://doi.org/10.26493/2590-9770.1745.5f4
(Also available at http://adam-journal.eu)
Generalization of edge general position problem*
Paul Manuel
Department of Information Science, College of Life Science, Kuwait University, Kuwait
R. Prabha
Department of Mathematics, Ethiraj College for Women, Chennai, Tamilnadu, India
Sandi Klavžar†
Faculty of Mathematics and Physics, University of Ljubljana, Slovenia and
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia and
Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
Dedicated to Dragan Marušič on the occasion of his 70th birthday.
Received 18 December 2023, accepted 27 January 2024, published online 20 February 2025
Abstract
The edge geodesic cover problem of a graph G is to find a smallest number of geodesics
that cover the edge set of G. The edge k-general position problem is introduced as the
problem to find a largest set S of edges of G such that at most k − 1 edges of S lie on
a common geodesic. We show that these are dual min-max problems and connect them
to an edge geodesic partition problem. Using these connections, exact values of the edge
k-general position number is determined for different values of k and for various networks
including torus networks, hypercubes, and Benes networks.
Keywords: General position set, edge geodesic cover problem, edge k-general position problem,
torus network, hypercube, Benes network.
Math. Subj. Class.: 05C12, 05C76
*We thank the reviewer for a very careful reading of the article. This work was supported and funded by
Kuwait University, Kuwait and the Research Project No. is FI 02/21.
†Corresponding author.
E-mail addresses: pauldmanuel@gmail.com (Paul Manuel), prabha75@gmail.com (R. Prabha),
sandi.klavzar@fmf.uni-lj.si (Sandi Klavžar)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 2590-9770
The Art of Discrete and Applied Mathematics 8 (2025) #P1.02
https://doi.org/10.26493/2590-9770.1745.5f4
(Dostopno tudi na http://adam-journal.eu)
Posplošitev povezavnega splošnega položajnega
problema*
Paul Manuel
Department of Information Science, College of Life Science, Kuwait University, Kuwait
R. Prabha
Department of Mathematics, Ethiraj College for Women, Chennai, Tamilnadu, India
Sandi Klavžar†
Fakulteta za matematiko in fiziko, Univerza v Ljubljani, Slovenijain
Inštitut za matematiko, fiziko in mehaniko, Ljubljana, Slovenija in
Fakulteta za naravoslovje in matematiko Univerze v Mariboru, Slovenija
Posvečeno Draganu Marušiču ob njegovi 70-letnici.
Prejeto 18. decembra 2023, sprejeto 27. januarja 2024, objavljeno na spletu 20. februarja 2025
Povzetek
Problem povezavnega geodetskega pokritja grafa G je: najti najmanjše število geodetk,
ki pokrivajo povezavno množico grafa G. Povezavni k-splošni položajni problem vpel-
jemo kot problem najti največjo množico S povezav grafa G z lastnostjo, da največ k − 1
njenih povezav leži na skupni geodetki. Pokažemo, da sta to dualna ekstremalna problema
iskanja minimuma oz. maksimuma, in ju povežemo s povezavnim particijskim proble-
mom. Na podlagi te povezave med problemoma določimo natančne vrednosti povezavnega
k-splošnega položajnega števila za različne vrednosti k in za različne mreže, vključno s
torusnimi mrežami, hiperkockami in Benesovimi mrežami.
Ključne besede: Splošna položajna množica, povezavni geodetski problem pokritja, povezavni k-
splošni položajni problem, torusna mreža, hiperkocka, Benesova mreža.
Math. Subj. Class.: 05C12, 05C76
*Recenzentu se zahvaljujemo za zelo natančno branje članka. To delo je podprla in financirala Kuvajtska
univerza, Kuvajt, št. raziskovalnega projekta pa je FI 02/21.
†Kontaktni avtor.
E-poštni naslovi: pauldmanuel@gmail.com (Paul Manuel), prabha75@gmail.com (R. Prabha),
sandi.klavzar@fmf.uni-lj.si (Sandi Klavžar)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/