On spanning trees whose degrees are congruent to one modulo $\ell$

Abstract

An $\ell$-congruent spanning tree of a nontrivial connected graph is a spanning tree in which every vertex has degree congruent to one modulo $\ell$. This notion provides a common generalization of classical spanning trees and odd spanning trees. We show, via a constructive greedy algorithm, that every $n$-vertex graph $G$ satisfying $n\equiv 2(\mathrm{mod}\ell )$ and $\delta (G)>\frac{(\ell -1)n}{\ell }$ has an $\ell$-congruent spanning tree. For the special case of odd spanning trees ($\ell =2$), our algorithmic approach simplifies the original proof by Zheng and Wu. We also derive formulas for the numbers of $\ell$-congruent spanning trees in complete graphs and complete bipartite graphs. These formulas specialize to the classical spanning-tree formulas when $\ell =1$ and to the corresponding odd-spanning-tree formulas when $\ell =2$.

12 pages