Spanning Trees with Bounded Maximum Degrees of Graphs on Surfaces

Source abstract

For a spanning tree $T$ of a graph $G$, we define the total excess $te(T,k)$ of $T$ from $k$ as $te(T,k) := \sum_{v \in V(T)} \max \{d_T(v)-k, 0\}$, where $d_T(v)$ is the degree of a vertex $v$ in $T$. In this paper, we show the following: if $G$ is a $3$-connected graph on a surface with Euler characteristic $\chi < 0$, then $G$ has a spanning $\lceil\frac{8-2\chi}{3}\rceil$-tree $T$ with $te(T, 3) \leq -2\chi-1$. We also show an application of this theorem to finding “light” connected subgraphs in a $3$-connected graph on a surface.