Electronic Journal of Linear Algebra • Vol 41
Edge-disjoint spanning trees and balloons in (multi-)graphs from size or spectral radius
August 2025 • Kun Cheng, Zihan Zhou
A multigraph is a graph that may have multiple edges, but has no loops. The multiplicity of a multigraph is the maximum number of edges between any pair of vertices. The spanning tree packing number of a graph $G$, denoted by $\tau(G)$, is the maximum number of edge-disjoint spanning trees contained in $G$. A balloon of a graph $G$ is a maximal 2-edge-connected subgraph that is joined to the rest of $G$ by exactly one cut edge. By $b(G)$, $e(G)$, and $\kappa(G)$, we denote the number of balloons, the size, and the…