{"id":"arxiv/2605.04725","url":"https://arxiv.org/abs/2605.04725","tags":["math.CO"],"score":0,"title":"The average distance of spanning trees in terms of independence number","domain":"math.CO","source":"arxiv","authors":["Zhibin Du","Xuli Qi"],"reviews":0,"subject":"math.CO","summary":"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 $μ(G)$, is defined to be the average of all distances between all pairs of vertices in $G$, i.e., $μ(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-06","reactions":{}}