Find subtrees of specified weight and cycles of specified length in linear time
On‐Hei Solomon Lo · Journal of Graph Theory · 2021
Abstract We apply the Euler tour technique to find subtrees of specified weight as follows. Let such that and , where . Let be a tree of vertices and let be vertex weights such that and for all . We prove that a subtree of of weight exists and can be found in linear time. We apply it to show, among others, the following: Every planar hamiltonian graph with minimum degree has a cycle of length for every with . Every 3‐connected planar hamiltonian graph with and even has a cycle of length or . Each of these cycles can be found in linear time if a Hamilton cycle of the graph is given. This study was partially motivated by conjectures of Bondy and Malkevitch on cycle spectra of 4‐connected planar graphs.