Spanning trees and spanning closed walks with small degrees

Abstract

Let $G$ be a graph and let $f$ be a positive integer-valued function on $V(G)$. In this paper, we show that if for all $S\subseteq V(G)$, $\omega (G\setminus S)<{\sum }_{v\in S}(f(v)-2)+2+\omega (G[S])$, then $G$ has a spanning tree $T$ containing an arbitrary given matching such that for each vertex $v$, $d_T(v)\le f(v)$, where $\omega (G\setminus S)$ denotes the number of components of $G\setminus S$ and $\omega (G[S])$ denotes the number of components of the induced subgraph $G[S]$ with the vertex set $S$. This is an improvement of several results. Next, we prove that if for all $S\subseteq V(G)$, $\omega (G\setminus S)\le {\sum }_{v\in S}(f(v)-1)+1$, then $G$ admits a spanning closed walk passing through the edges of an arbitrary given matching meeting each vertex $v$ at most $f(v)$ times. This result solves a long-standing conjecture due to Jackson and Wormald (1990).

arXiv comment22 pages: Some removed parts of former versions will be published in some new papers