pith. sign in

arxiv: 2605.04725 · v1 · submitted 2026-05-06 · 🧮 math.CO

The average distance of spanning trees in terms of independence number

Zhibin Du , Xuli Qi This is my paper

Pith reviewed 2026-05-08 16:33 UTC · model grok-4.3

classification 🧮 math.CO
keywords spanning treesaverage distanceindependence numberupper boundsasymptotic sharpnessconnected graphsgraph distancestree metrics
0
0 comments X

The pith

Any connected graph with independence number α has a spanning tree with average pairwise distance less than α + 1.

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

In any connected graph one can always select a spanning tree whose average pairwise distance is strictly less than the independence number plus one. This removes an earlier restriction that the number of vertices must exceed twice the independence number minus one and improves the previous bound of α + 2. For independence numbers seven and larger the authors obtain a stricter inequality, α + 1/2 + 4(α − 1)/α². They further show that the new upper bound is asymptotically the best possible once both the order of the graph and α become large.

Core claim

We prove that every connected graph G with independence number α admits a spanning tree T satisfying μ(T) < α + 1. Moreover, when α ≥ 7 we establish the stronger inequality μ(T) < α + 1/2 + 4(α − 1)/α². These upper bounds on the minimum average distance among spanning trees are asymptotically sharp.

What carries the argument

A spanning tree built from a maximum independent set of size α whose edge connections limit long paths and thereby keep the average of all pairwise distances below α + 1.

If this is right

  • The minimum-average-distance spanning tree problem admits an explicit upper bound expressed solely in terms of the independence number.
  • The earlier vertex-order condition n > 2α − 1 is no longer required.
  • For large α the average distance of the chosen tree is forced to lie asymptotically at most α from above.
  • The result supplies a uniform guarantee for all connected graphs, independent of their total size.

Where Pith is reading between the lines

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

  • The construction may supply practical heuristics for low-cost spanning trees in networks whose maximum independent sets are large.
  • Similar distance-control arguments could be examined for other graph invariants such as clique number or chromatic number.
  • Explicit checks on families such as bipartite graphs or threshold graphs would test how close the bound comes to being achieved.

Load-bearing premise

A maximum independent set of size α can always be used to construct a spanning tree in which most vertex pairs remain close enough on average.

What would settle it

A connected graph with independence number α in which every spanning tree has average distance at least α + 1.

Figures

Figures reproduced from arXiv: 2605.04725 by Xuli Qi, Zhibin Du.

Figure 1
Figure 1. Figure 1: a 1 v 1  v 2 v a v 2 b            2 b            view at source ↗
Figure 2
Figure 2. Figure 2: The tree T in Lemma 3.1. Proof. If |V (P)| ≥ |V (Q)|, then W(Tw) − W(T) = |V (M)|(|V (P)| − |V (Q)| + 1) > 0. If |V (P)| < |V (Q)|, then similarly W(Tu) − W(T) = |V (M)|(|V (Q)| − |V (P)| + 1) > 0. The result holds clearly. □ Remark 3.1 If we insert one vertex between v and u, and another vertex between v and w, the tree under consideration is as depicted in view at source ↗
Figure 3
Figure 3. Figure 3: The tree T in Remark 3.1. Remark 3.2 It is easy to verify that the upper bound 1 12 (2n 3 − (3p 2 − 6p + 2)n + p 3 + 3p 2 − 10p) on W(T) claimed in Lemma 3.2 is decreasing for p ≥ 1 (by checking its derivative with respect to p is negative). Let Ta,b be the set of trees of order a+b obtained from a tree H of order a by attaching b pendent vertices to some vertices of H, where a ≥ 2 and b ≥ 1. Mukwembi [26]… view at source ↗
Figure 4
Figure 4. Figure 4: The tree T used in the proof of Lemma 5.3. It is not hard to verify that W(T) is increasing in a ≤ n−2k+1 k (since n−2k+1 k ≤ n−3 2 ), thus the maximum value of W(T) is attained at a = n−2k+1 k . Substitute a = n−2k+1 k into (1), the upper bound of W(T) would be expressed in terms of a quadratic function on b as W(T) ≤ f(b) 3k 2 , where f(b) = −3k 2 (2k − 3)b 2 + 3k 2 (2k − 3)(n − 2k + 2)b + 3(k 2 + 2k − 2… view at source ↗
Figure 5
Figure 5. Figure 5: The tree T used in the proof of Lemma 5.4. +c(n − c − 2) + (c + 1)(n − c − 3) = (n − 1)2 + 2 X k−7 i=0 ((n − 2k + 1 − b − c) + i)(n − (n − 2k + 1 − b − c) − i − 2) +b(n − b − 2) + (b + 1)(n − b − 3) + c(n − c − 2) + (c + 1)(n − c − 3). (2) Analogous to the handling of (1) in the proof of Lemma 5.3 (in a more complicated form), the maximum value of W(T) would be attained at b = c = (k − 2)n − 2k 2 + 3k + 6 … view at source ↗
read the original abstract

Let $G$ be a connected graph with vertex set $V(G)$, and denote by $d_G(u,v)$ the distance from $u$ to $v$ in $G$, for any $u,v \in V(G)$. The average distance of an $n$-vertex connected graph $G$, denoted by $\mu(G)$, is defined to be the average of all distances between all pairs of vertices in $G$, i.e., $\mu (G) = \binom{n}{2}^{-1} \sum_{\{u,v\} \subset V(G)}d_G(u,v)$. The problem of finding a spanning tree of minimum average distance is known to be NP-hard, so establishing an upper bound for the minimum average distance among all spanning trees is of particular interest. Mukwembi (J. Graph Theory, 2014) showed that if $G$ is a connected graph of order $n$ with independence number $\alpha$, where $n > 2 \alpha - 1$, then $G$ has a spanning tree $T$ such that $\mu(T) \le \alpha + 2$. In this paper, we first improve the upper bound to $\mu(T) < \alpha + 1$ for $\alpha \ge 1$, and then we find the bound could be further improved when $\alpha$ becomes larger, so a better upper bound \[ \mu(T) < \left\{ \begin{array}{ll} \alpha+1 & \hbox{if } 1\le\alpha\le 6,\\ \alpha+\frac12+\frac{4(\alpha-1)}{\alpha^2} & \hbox{if } \alpha\ge 7, \end{array} \right. \] is established later. In the end, we give a remark to indicate our new upper bound is best possible in the sense of asymptotics (when $n$ and $\alpha$ are large enough).

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

1 major / 0 minor

Summary. The paper claims that every connected graph G with independence number α ≥ 1 admits a spanning tree T with average distance μ(T) < α + 1. For α ≥ 7 the bound is sharpened to μ(T) < α + 1/2 + 4(α−1)/α². These results improve Mukwembi’s 2014 theorem (which required n > 2α − 1 and obtained μ(T) ≤ α + 2). The authors also assert that the new upper bound is asymptotically tight for large n and α.

Significance. If the proofs are valid, the work supplies a cleaner and quantitatively stronger upper bound on the minimum average distance of any spanning tree, expressed only in terms of α. The asymptotic-optimality remark is a useful addition, as it indicates that the leading term cannot be improved.

major comments (1)
  1. [Main theorem and its proof] The main theorem (stated in the abstract and proved in the body) asserts the bound μ(T) < α + 1 for every connected G with independence number α, without the hypothesis n > 2α − 1 that appeared in Mukwembi’s result. The standard construction selects a maximum independent set S and attaches the components of G − S to S. When n ≤ 2α − 1 the number of such components can reach α − 1, and the resulting tree distances between vertices in distinct components are at most 2 or 3; the paper does not explicitly verify that the claimed additive constants remain valid in this regime.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need to explicitly address the regime n ≤ 2α − 1. We agree that a dedicated verification strengthens the presentation and will incorporate it in the revision.

read point-by-point responses

  1. Referee: The main theorem (stated in the abstract and proved in the body) asserts the bound μ(T) < α + 1 for every connected G with independence number α, without the hypothesis n > 2α − 1 that appeared in Mukwembi’s result. The standard construction selects a maximum independent set S and attaches the components of G − S to S. When n ≤ 2α − 1 the number of such components can reach α − 1, and the resulting tree distances between vertices in distinct components are at most 2 or 3; the paper does not explicitly verify that the claimed additive constants remain valid in this regime.

    Authors: The proof of Theorem 1 in Section 3 proceeds by selecting a maximum independent set S of size α and constructing a spanning tree T by attaching each component of G − S to a distinct vertex of S (possible because G is connected). This construction is valid for all n ≥ α + 1 without any further restriction on n. When n ≤ 2α − 1, G − S has at most α − 1 vertices, so at most α − 1 components; the resulting distances in T between vertices in distinct components are indeed at most 3. Because the total number of pairs is binomial(n,2) and n is linear in α, the contribution of these longer pairs to the average is bounded by a quantity strictly less than 1. Consequently μ(T) < α + 1 continues to hold. We acknowledge that the original manuscript did not isolate this short case for explicit verification. In the revised version we will insert a short paragraph immediately after the main construction that carries out the (straightforward) calculation for n ≤ 2α − 1, confirming the strict inequality. This change does not alter the theorem statement or the asymptotic tightness remark. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bounds from explicit constructions

full rationale

The paper derives its upper bounds on μ(T) via combinatorial constructions: select a maximum independent set S of size α, then attach components of G-S to S while controlling tree distances. These steps produce the stated inequalities (μ(T) < α+1, and the refined form for α≥7) directly from distance counting in the resulting tree, without reducing to fitted parameters, self-definitions, or load-bearing self-citations. The asymptotic optimality remark is supported by explicit examples rather than circular renaming. The extension beyond Mukwembi's n>2α−1 hypothesis is handled by case analysis on component attachments, keeping the argument self-contained against the graph inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Relies on standard graph theory definitions without new free parameters or invented entities.

axioms (1)
  • standard math Standard definitions of connected graph, distance d_G(u,v), spanning tree, independence number α, and average distance μ(G).
    These are foundational concepts invoked throughout the abstract and prior literature.

pith-pipeline@v0.9.0 · 5659 in / 1181 out tokens · 66039 ms · 2026-05-08T16:33:46.004378+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

32 extracted references · 32 canonical work pages

  1. [1]

    Beezer, J.E

    R.A. Beezer, J.E. Riegsecker, B.A. Smith, Using minimum degree to bound average distance, Discrete Math. 226 (2001) 365–371

    work page 2001

  2. [2]

    Buckley, F

    F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley, Redwood, 1990

    work page 1990

  3. [3]

    Y.-Z. Chen, X. Li, X.-D. Zhang, The extremal average distance of cubic graphs, J. Graph Theory 103 (2023) 713–739

    work page 2023

  4. [4]

    Chung, The average distance and the independence number, J

    F.R.K. Chung, The average distance and the independence number, J. Graph Theory 12 (1988) 229–235

    work page 1988

  5. [5]

    Dankelmann, Average distance and independence number, Discrete Appl

    P. Dankelmann, Average distance and independence number, Discrete Appl. Math. 51 (1994) 75–83

    work page 1994

  6. [6]

    Dankelmann, Average distance and domination number, Discrete Appl

    P. Dankelmann, Average distance and domination number, Discrete Appl. Math. 80 (1997) 21–35

    work page 1997

  7. [7]

    Dankelmann, Average distance in weighted graphs, Discrete Math

    P. Dankelmann, Average distance in weighted graphs, Discrete Math. 312 (2012) 12–20

    work page 2012

  8. [8]

    Dankelmann, R

    P. Dankelmann, R. Entringer, Average distance, minimum degree, and spanning trees, J. Graph Theory 33 (2000) 1–13

    work page 2000

  9. [9]

    Dankelmann, S

    P. Dankelmann, S. Mukwembi, H.C. Swart, Average distance and vertex-connectivity, J. Graph Theory 62 (2009) 157–177

    work page 2009

  10. [10]

    Dankelmann, O.R

    P. Dankelmann, O.R. Oellermann, J.-L. Wu, Minimum average distance of strong orientations of graphs, Discrete Appl. Math. 143 (2004) 204–212

    work page 2004

  11. [11]

    DeLaVi˜ na, R

    E. DeLaVi˜ na, R. Pepper, B. Waller, A note on dominating sets and average distance, Discrete Math. 309 (2009) 2615–2619

    work page 2009

  12. [12]

    Dobrynin, R

    A.A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: Theory and appli- cations, Acta Appl. Math. 66 (2001) 211–249

    work page 2001

  13. [13]

    Du, Wiener indices of trees and monocyclic graphs with given bipartition, Int

    Z. Du, Wiener indices of trees and monocyclic graphs with given bipartition, Int. J. Quantum. Chem. 112 (2013) 1598–1605

    work page 2013

  14. [14]

    Z. Du, A. Ili´ c, L. Feng, Further results on the distance spectral radius of graphs, Linear Multilinear Algebra 61 (2013) 1287–1301. 19

    work page 2013

  15. [15]

    Z. Du, B. Zhou, Minimum Wiener indices of trees and unicyclic graphs of given matching number, MATCH Commun. Math. Comput. Chem. 63 (2010) 101–112

    work page 2010

  16. [16]

    Entringer, Bounds for the average distance-inverse degree product in trees, In: Y

    R.C. Entringer, Bounds for the average distance-inverse degree product in trees, In: Y. Alavi, D.R. Lick, A.J. Schwenk (eds), Combinatorics, Graph Theory, and Algorithms, New Issues Press, Kalamazoo, 1999, pp. 335–352

    work page 1999

  17. [17]

    Entringer, D.J

    R.C. Entringer, D.J. Kleitman, L.A. Sz´ ekely, A note on spanning trees with minimum average distance, Bull. Inst. Combin. Appl. 17 (1996) 71–78

    work page 1996

  18. [18]

    Fajtlowicz, W

    S. Fajtlowicz, W. Waller, On two conjectures of Graffiti I, Congr. Numer. 55 (1986) 51–56

    work page 1986

  19. [19]

    Fajtlowicz, W

    S. Fajtlowicz, W. Waller, On two conjectures of Graffiti II, Congr. Numer. 60 (1987) 187–197

    work page 1987

  20. [20]

    Gutman, O.E

    I. Gutman, O.E. Polansky, Mathematical Concepts in Organic Chemistry, Springer– Verlag, Berlin, 1986

    work page 1986

  21. [21]

    Hansen, A

    P. Hansen, A. Hertz, R. Kilani, O. Marcotte, D. Schindl, Average distance and maximum induced forest, J. Graph Theory 60 (2009) 31–54

    work page 2009

  22. [22]

    Hendry, Existence of graphs with prescribed mean distance, J

    G.R.T. Hendry, Existence of graphs with prescribed mean distance, J. Graph Theory 10 (1986) 173–175

    work page 1986

  23. [23]

    Hu, Optimum communication spanning trees, SIAM J

    T.C. Hu, Optimum communication spanning trees, SIAM J. Comput. 3 (1974) 188– 195

    work page 1974

  24. [24]

    Johnson, J.K

    D.S. Johnson, J.K. Lenstra, A.H.G.R. Kan, The complexity of the network design problem, Networks 8 (1978) 279–285

    work page 1978

  25. [25]

    Kouider, P

    M. Kouider, P. Winkler, Mean distance and minimum degree, J. Graph Theory 25 (1997) 95–99

    work page 1997

  26. [26]

    Mukwembi, Average distance, independence number, and spanning trees, J

    S. Mukwembi, Average distance, independence number, and spanning trees, J. Graph Theory 76 (2014) 194–199

    work page 2014

  27. [27]

    Mukwembi, Average distance, minimum degree, and irregularity index, Discrete Math

    S. Mukwembi, Average distance, minimum degree, and irregularity index, Discrete Math. 347 (2024) 113671

    work page 2024

  28. [28]

    Nikoli´ c, N

    S. Nikoli´ c, N. Trinajsti´ c, Z. Mihali´ c, The Wiener index: Development and applica- tions, Croat. Chem. Acta 68 (1995) 105–128

    work page 1995

  29. [29]

    Plesn´ ık, On the sum of all distances in a graph or digraph, J

    J. Plesn´ ık, On the sum of all distances in a graph or digraph, J. Graph Theory 8 (1984) 1–21

    work page 1984

  30. [30]

    Shi, The average distance of trees, System Sci

    R. Shi, The average distance of trees, System Sci. Math. Sci. 6 (1993) 18–24. 20

    work page 1993

  31. [31]

    Wiener, Structural determination of paraffin boiling points, J

    H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20

    work page 1947

  32. [32]

    Y.-N. Yeh, I. Gutman, On the sum of all distances in composite graphs, Discrete Math. 135 (1994) 359–365. 21

    work page 1994