EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Counting Geodesic Paths in Graphs

Martin Knor, Jelena Sedlar, Riste Škrekovski, Xiao-Dong Zhang

Mediterranean Journal of Mathematics · 2026-08 · 23 (5)

DOI: 10.1007/s00009-026-03159-3 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mediterranean Journal of Mathematics, online erschienen am 01.08.2026. Verfasst von Martin Knor und 3 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Vedecká Grantová Agentúra MŠVVaŠ SR a SAV, Agentúra na Podporu Výskumu a Vývoja, The Slovenian Research and Innovation Agency.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A geodesic is a shortest path which connects a pair of vertices of a graph G . In this paper, we define the geodesic subpath number $$\textrm{gpn}(G)$$ gpn ( G ) of a graph G as the number of geodesics in G . The number of subtrees and subpaths are already studied in the literature, but they are both large quantities. Hence, the geodesic subpath number which is related to these quantities but smaller than both seems worthy of investigation. We first consider extremal graphs with respect to the geodesic subpath number among all connected graphs on n vertices. This number is minimized by the so-called geodetic graphs, i.e., graphs in which each pair of vertices is connected by precisely one geodesic. As for the graphs which maximize the geodesic subpath number, we provide an upper bound on $$\textrm{gpn}(G)$$ gpn ( G ) in terms of n and we further consider several graph families which might have a large $$\textrm{gpn}(G)$$ gpn ( G ) . Yet, their value of $$\textrm{gpn}(G)$$ gpn ( G ) still does not attain the established bound, so narrowing the gap remains as an open problem. We also consider the class of cactus graphs on n vertices and k cycles and among them characterize extremal graphs with respect to this new invariant.

Förderung

  • Vedecká Grantová Agentúra MŠVVaŠ SR a SAV
  • Agentúra na Podporu Výskumu a Vývoja
  • The Slovenian Research and Innovation Agency
  • Ministarstvo Znanosti, Obrazovanja i Sporta
  • European Regional Development Fund, European Union
  • Hrvatska Zaklada za Znanost
  • NextGenerationEU
  • National Natural Science Foundation of China

Zitieren

APA

Knor, M., Sedlar, J., Škrekovski, R., & Zhang, X. (2026). Counting Geodesic Paths in Graphs. Mediterranean Journal of Mathematics, 23(5). https://doi.org/10.1007/s00009-026-03159-3

Vancouver

Knor M, Sedlar J, Škrekovski R, Zhang X. Counting Geodesic Paths in Graphs. Mediterranean Journal of Mathematics. 2026;23(5). doi:10.1007/s00009-026-03159-3

BibTeX
@article{Knor2026,
  author = {Knor, Martin and Sedlar, Jelena and Škrekovski, Riste and Zhang, Xiao-Dong},
  title = {Counting Geodesic Paths in Graphs},
  journal = {Mediterranean Journal of Mathematics},
  year = {2026},
  volume = {23},
  number = {5},
  doi = {10.1007/s00009-026-03159-3}
}
Kostenlos starten →