English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We apply the Euler tour technique to find subtrees of specified weight asfollows. Let $k, g, N_1, N_2 \in \mathbb{N}$ such that $1 \leq k \leq N_2$, $g+ h > 2$ and $2k - 4g - h + 3 \leq N_2 \leq 2k + g + h - 2$, where $h := 2N_1 -N_2$. Let $T$ be a tree of $N_1$ vertices and let $c : V(T) \rightarrow\mathbb{N}$ be vertex weights such that $c(T) := \sum_{v \in V(T)} c(v) = N_2$and $c(v) \leq k$ for all $v \in V(T)$. We prove that a subtree $S$ of $T$ ofweight $k - g + 1 \leq c(S) \leq k$ exists and can be found in linear time. Weapply it to show, among others, the following: (i) Every planar hamiltoniangraph $G = (V(G), E(G))$ with minimum degree $\delta \geq 4$ has a cycle oflength $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)|$. (ii) Every$3$-connected planar hamiltonian graph $G$ with $\delta \geq 4$ and $|V(G)|\geq 8$ even has a cycle of length $\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 ofthe graph is given. This work was partially motivated by conjectures of Bondyand Malkevitch on cycle spectra of 4-connected planar graphs.

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