Find Subtrees of Specified Weight and Cycles of Specified Length in Linear Time

We apply the Euler tour technique to find subtrees of specified weight as follows. Let $k,g,N_1,N_2\in \mathbb{N}$ such that $1\le k\le N_2$, $g

• h > 2$and$2k - 4g - h + 3 \leq N_2 \leq 2k + g + h - 2$,where$h := 2N_1 - N_2$\mathrm{.}Let$T$beatreeof$N_1$verticesandlet$c : V(T) \rightarrow $\mathbb{N}$$bevertexweightssuchthat$c(T) := \sum_{v \in V(T)} c(v) = N_2$and$c(v) \leq k$forall$v \in V(T)$\mathrm{.}Weprovethatasubtree$S$of$T$ of weight $k-g+1\le c(S)\le k$ exists and can be found in linear time. We apply it to show, among others, the following: (i) Every planar hamiltonian graph $G=(V(G),E(G))$ with minimum degree $\delta \ge 4$ has a cycle of length $k$ for every $k \in {\lfloor \frac{|V(G)|}{2} \rfloor, \dots, \lceil \frac{|V(G)|}{2} \rceil + 3}$with$3 \leq k \leq |V(G)|$\mathrm{.}(ii)Every$3$-connectedplanarhamiltoniangraph$G$with$\delta \geq 4$and$|V(G)| \geq 8$evenhasacycleoflength$\frac{|V(G)|}{2} - 1$or$\frac{|V(G)|}{2}

• 2$. Each of these cycles can be found in linear time if a Hamilton cycle of the graph is given. This work was partially motivated by conjectures of Bondy and Malkevitch on cycle spectra of 4-connected planar graphs.