Water Transport on 3-Spiders: Unbounded Lengths of Shortest Optimal Strategies
Abstract
Let G be a finite simple graph. An averaging operation selects a nonempty connected vertex set and replaces the weights of its vertices by their arithmetic mean. For a nonnegative initial weight function ω:V(G)→ℝ≥0 and a target vertex x, let t(G,x,ω) denote the minimum number of averaging operations needed to attain the maximum reachable weight at x. Gollin et al.[1] proved, using the Axiom of Choice, that a finite optimal strategy exists for every finite graph, every nonnegative initial weight function and every target vertex; see Tao [2] for a simplified proof. We prove that the lengths of shortest optimal strategies on $3$-spiders have no uniform finite bound. In particular, these lengths cannot be bounded in terms of the maximum degree of the graph.
Related
- The shortest harmonic sums with decreasing denominator
- Schur positivity from signed elementary expansions: clique-spiders and spiders S(a,b,2)
- Smoothness of Shortest Isogenies to Frobenius Conjugates
- The Maximum Number of Shortest Paths in Graphs
- Shortest closed geodesics on three-dimensional isospectral manifolds
BibTeX
@misc{chen2026water,
title = {{Water Transport on 3-Spiders: Unbounded Lengths of Shortest Optimal Strategies}},
author = {Guanheng Chen and Ran Tao and Tianyi Tao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31499},
eprint = {2610.31499},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31499},
}
RIS
TY - UNPB
TI - Water Transport on 3-Spiders: Unbounded Lengths of Shortest Optimal Strategies
AU - Guanheng Chen
AU - Ran Tao
AU - Tianyi Tao
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31499
UR - https://arxiv.org/abs/2610.31499
AB - Let G be a finite simple graph. An averaging operation selects a nonempty connected vertex set and replaces the weights of its vertices by their arithmetic mean. For a nonnegative initial weight function ω:V(G)→ℝ_≥0 and a target vertex x, let t(G,x,ω) denote the minimum number of averaging operations needed to attain the maximum reachable weight at x. Gollin et al.[1] proved, using the Axiom of Choice, that a finite optimal strategy exists for every finite graph, every nonnegative initial weight function and every target vertex; see Tao [2] for a simplified proof. We prove that the lengths of shortest optimal strategies on $3$-spiders have no uniform finite bound. In particular, these lengths cannot be bounded in terms of the maximum degree of the graph.
ER -