pith. sign in

arxiv: 2604.04907 · v1 · submitted 2026-04-06 · 🧮 math.CO

Counting geodesic paths in graphs

Martin Knor , Jelena Sedlar , Riste \v{S}krekovski , Xiao-Dong Zhang This is my paper

Pith reviewed 2026-05-10 19:22 UTC · model grok-4.3

classification 🧮 math.CO
keywords geodesic subpath numbergeodetic graphscactus graphsextremal graphsshortest pathsgraph theorycombinatorics
0
0 comments X

The pith

Geodetic graphs minimize the geodesic subpath number among connected graphs on n vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the geodesic subpath number gpn(G) as the total number of shortest paths between all pairs of vertices in G. It establishes that this number is minimized by geodetic graphs, which have exactly one geodesic between any pair of vertices. An upper bound is given for gpn(G) in terms of n, but the examined graph families do not reach this bound, posing an open problem. Extremal graphs are also characterized within the class of cactus graphs having n vertices and k cycles. This provides a new way to measure path multiplicity in graphs that is smaller than the counts of all subpaths or subtrees.

Core claim

We introduce gpn(G) as the number of geodesics in G. This quantity is minimized by the geodetic graphs. We establish an upper bound on gpn(G) and investigate several families that could maximize it without attaining the bound. We also find the extremal members among cactus graphs on n vertices with k cycles.

What carries the argument

gpn(G), the count of all shortest paths in the graph G

If this is right

  • Every connected graph has at least as many geodesics as there are pairs of vertices.
  • The minimum is achieved exactly by graphs with unique shortest paths between all pairs.
  • Within cactus graphs, the extremal structures for gpn depend on the number of cycles k.
  • The gap between the upper bound and actual maxima suggests room for graphs with higher path multiplicity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Applications in communication networks might favor geodetic graphs to ensure unique routing paths.
  • This measure could be extended to weighted graphs or directed graphs for broader use in optimization.
  • Relating gpn to other invariants like the Wiener index might yield new bounds.

Load-bearing premise

That the upper bound provided is tight enough to be meaningful despite not being achieved by any known family.

What would settle it

Finding a graph on n vertices with gpn(G) larger than the derived upper bound would disprove the bound; observing a graph with gpn below the minimum for its class would challenge the extremal results for cacti.

Figures

Figures reproduced from arXiv: 2604.04907 by Jelena Sedlar, Martin Knor, Riste \v{S}krekovski, Xiao-Dong Zhang.

Figure 1
Figure 1. Figure 1: The figure shows two cactus graphs and the unipath structures of these graphs [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The figure shows a unipath resolved cactus graph. It contains two unipath [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 1
Figure 1. Figure 1: b). Notice that every pair of vertices x and y is connected by the same number of shortest paths in G and G′ , so gpn(G′ ) = gpn(G). Case 2. H contains a single squared vertex which is shared by at least two squares. An example of such structure are both unipath structures of the graph in [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: The figure shows a squared chain. A vertex of G ∈ Cn,k is multisquared (resp. bisquared) if it belongs to at least two (resp. precisely two) squares. A squared chain is a unipath resolved cactus graph in which every multisquared vertex is bisquared. An example of squared chain is shown in [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The figure shows all maximal cacti for n = 17 and k = 7 [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The figure shows all maximal cacti for n = 9 and k = 2. 20 [PITH_FULL_IMAGE:figures/full_fig_p020_5.png] view at source ↗
read the original abstract

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 gpn(G) of a graph G as the number of geodesics in G. The number of subtrees and subpaths are already studied in 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 gpn(G) in terms of n and we further consider several graph families which might have a large gpn(G). Yet, their value of 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper defines the geodesic subpath number gpn(G) as the total number of geodesics (shortest paths) over all vertex pairs in a connected graph G. It establishes that gpn(G) is minimized by geodetic graphs, where each pair has exactly one geodesic and thus gpn(G) equals binom(n,2) for n-vertex graphs. An upper bound on gpn(G) in terms of n is derived, although the bound is not attained by the families examined and the problem of determining the maximum remains open. For the subclass of cactus graphs with n vertices and k cycles, the paper characterizes the graphs that extremize gpn(G).

Significance. The minimization result follows directly from the definition and correctly identifies geodetic graphs as the unique minimizers. The explicit upper bound, even if not tight, supplies a concrete theoretical ceiling and the open gap is stated transparently. The characterization for cactus graphs supplies a complete extremal result within a well-defined family. These contributions are proportionate to the new invariant and could usefully connect to existing work on shortest-path enumeration and network reliability.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'the number of subtrees and subpaths are already studied in literature' would benefit from one or two specific citations to prior results on subtree and subpath enumeration so that the relation to gpn(G) is immediately contextualized.
  2. [Upper bound section] Upper-bound section: the explicit functional form of the claimed upper bound in terms of n should be displayed as a numbered equation rather than described only in prose, to facilitate future comparisons and tighten the open-problem statement.
  3. [Cactus graphs section] Cactus characterization: a short table or figure listing the extremal cactus graphs for small (n,k) pairs (e.g., n=6, k=2) would make the structural description easier to verify and would illustrate the difference between the minimizing and maximizing cases.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive overall assessment. The referee summary accurately captures the main results, and we appreciate the recognition that the open problem on the maximum is stated transparently. As no specific major comments or requested changes were listed, we have no revisions to propose at this stage.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper defines gpn(G) directly as the total number of geodesics (shortest paths) across all vertex pairs in a connected graph on n vertices. The minimization statement follows immediately from this definition: every connected graph has at least one geodesic per pair, so gpn(G) is at least binom(n,2), with equality exactly when the graph is geodetic (one geodesic per pair). The upper bound is stated explicitly as unattained by the families considered, with the gap left open. No equations reduce any claimed extremal value or characterization to a fitted parameter, self-citation chain, or ansatz imported from prior work by the same authors. The cactus-graph analysis and extremal characterizations use standard counting arguments on standard graph families without internal reduction to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The paper rests on ordinary graph-theory definitions and introduces one new counting function with no fitted numerical parameters.

axioms (2)
  • standard math Graphs are finite, undirected, and simple unless otherwise stated.
    Invoked throughout the definition of geodesics and the extremal problems.
  • standard math A geodesic between two vertices is any shortest path connecting them.
    Directly used to define gpn(G) as the total number of such paths.
invented entities (1)
  • geodesic subpath number gpn(G) no independent evidence
    purpose: To count the aggregate number of geodesics over all vertex pairs.
    Newly defined object whose extremal behavior is the paper's main subject.

pith-pipeline@v0.9.0 · 5512 in / 1185 out tokens · 65909 ms · 2026-05-10T19:22:23.634853+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Atajan, X

    T. Atajan, X. Yong, H. Inaba, An efficient approach for counting the number of spanning trees in circulant and related graphs,Discrete Math.310(2010) 1210–1221

    work page 2010

  2. [2]

    R. B. Bapat, A. K. Lal, S. Pati, Laplacian spectrum of weakly quasi-threshold graphs, Graphs Comb.24(2008) 273–290

    work page 2008

  3. [3]

    T. J. N. Brown, R. B. Mallion, P. Pollak, A. Roth, Some methods for counting the spanning trees in labeled molecular graphs, examined in relation to certain fullerenes, Discrete Appl. Math.67(1996) 51–66

    work page 1996

  4. [4]

    Cornelsen, M

    S. Cornelsen, M. Pfister, H. F¨ orster, M. Gronemann, M. Hoffmann, S. Kobourov, T. Schneck, Drawing shortest paths in geodetic graphs,J. Graph Algorithms Appl. 26(3)(2022) 353–361

    work page 2022

  5. [5]

    Czabarka, L

    ´E. Czabarka, L. Sz´ ekely, S. Wagner, The inverse problem for certain tree parameters, Discrete Appl. Math.157(15)(2009) 3314–3319

    work page 2009

  6. [6]

    Elder, A

    M. Elder, A. Piggott, Rewriting systems, plain groups, and geodetic graphs,Theor. Comput. Sci.903(2022) 134-144

    work page 2022

  7. [7]

    Q. Feng, Y. Peng, W. Zhang, X. Lin, Y. Zhang, DSPC: Efficiently Answering Shortest Path Counting on Dynamic Graphs,Proceedings of the 27th International Conference on Extending Database Technology (EDBT)(2024) 116–128

    work page 2024

  8. [8]

    Gorovoy, D

    D. Gorovoy, D. Zmiaikou, On graphs with unique geodesics and antipodes,Discrete Math.347(4)(2024) 113864

    work page 2024

  9. [9]

    R. Kirk, H. Wang, Largest number of subtrees of trees with a given maximum degree, SIAM J. Discrete Math.22(2008) 985–995

    work page 2008

  10. [10]

    M. Knor, J. Sedlar, R. ˇSkrekovski, Y. Yang, Invitation to the subpath number, arXiv:2503.00558 [math.CO]

    work page arXiv

  11. [11]

    M. Knor, J. Sedlar, R. ˇSkrekovski, Y. Yang, The subpath number of cactus graphs, arXiv:2503.02683 [math.CO]

    work page arXiv

  12. [12]

    M. Knor, R. ˇSkrekovski, A. Tepeh, Mathematical aspects of Wiener index,Ars Math. Contemp.11(2016) 327–352

    work page 2016

  13. [13]

    M. Knor, R. ˇSkrekovski, A. Tepeh, Selected topics on Wiener index,Ars Math. Contemp.(2024) #P4.07. 22

    work page 2024

  14. [14]

    Metric dimension related parameters in graphs: A survey on combinatorial, computa- tional and applied results, arXiv:2107.04877 [math.CO] (10 Jul 2021)

    D. Kuziak, I. G. Yero, Metric dimension related parameters in graphs: A sur- vey on combinatorial, computational and applied results. (2021) arXiv preprint arXiv:2107.04877 [math.CO]

    work page arXiv 2021

  15. [15]

    J. Li, K. Xu, T. Zhang, H. Wang, S. Wagner, Maximum number of subtrees in cacti and block graphs,Aequat. Math.96(2022) 1027–1040

    work page 2022

  16. [16]

    S. D. Nikolopoulos, L. Palios, C. Papadopoulos, Counting spanning trees using mod- ular decomposition,Theor. Comput. Sci.526(2014) 41–57

    work page 2014

  17. [17]

    S. D. Nikolopoulos, P. Rondogiannis, On the number of spanning trees of multi-star related graphs,Inf. Process. Lett.65(1998) 183–188

    work page 1998

  18. [18]

    Ore, Theory of Graphs, Amer

    Ø. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, RI, 1962

    work page 1962

  19. [19]

    Y. Peng, J. X. Yu, S. Wang, PSPC: Efficient Parallel Shortest Path Counting on Large-Scale Graphs,Proceedings of the 39th IEEE International Conference on Data Engineering (ICDE)(2023) 896–908

    work page 2023

  20. [20]

    Peterin, J

    I. Peterin, J. Sedlar, R. ˇSkrekovski, I. G. Yero, Resolving vertices of graphs with differences,Comput. Appl. Math.43 (5)(2024) 275

    work page 2024

  21. [21]

    Y. Qiu, R. Jin, Z. Zhao, Efficient Shortest Path Counting on Large Road Networks, Proceedings of the VLDB Endowment15(10)(2022) 2098–2110

    work page 2022

  22. [22]

    L. A. Sz´ ekely, H. Wang, On subtrees of trees,Adv. Appl. Math.34(2005) 138–155

    work page 2005

  23. [23]

    L. A. Sz´ ekely, H. Wang, Binary trees with the largest number of subtrees,Discrete Appl. Math.155(2007) 374–385

    work page 2007

  24. [24]

    K. Xu, J. Li, H. Wang, The number of subtrees in graphs with given number of cut edges,Discrete Appl. Math.304(2021) 283–296

    work page 2021

  25. [25]

    Yamamoto, Approximately counting paths and cycles in a graph,Discrete Appl

    M. Yamamoto, Approximately counting paths and cycles in a graph,Discrete Appl. Math.217(2009) 381–387

    work page 2009

  26. [26]

    W.-M. Yan, W. Myrvold, K.-L. Chung, A formula for the number of spanning trees of a multi-star related graph,Inf. Process. Lett.68(1998) 295–298

    work page 1998

  27. [27]

    X. M. Zhang, X. D. Zhang, D. Gray, H. Wang, The number of subtrees of trees with given degree sequence,J. Graph Theory73(2013) 280–295. 23

    work page 2013