Paper Info
Title
Find Subtrees Of Specified Weight And Cycles Of Specified Length In Linear Time
Abstract
We apply the Euler tour technique to find subtrees of specified weight as follows. Let k , g , N 1 , N 2 is an element of N such that 1 <= k <= N 2 ,g + h > 2 and 2 k - 4 g - h + 3 <= N 2 <= 2 k + g + h - 2, where h colon equals 2 N 1 - N 2. Let T be a tree of N 1 vertices and let c : V ( T ) -> N be vertex weights such that c ( T ) colon equals n-ary sumation v is an element of V ( T ) c ( v ) = N 2 and c ( v ) <= k for all v is an element of V ( T ). We prove that a subtree S of T of weight k - g + 1 <= c ( S ) <= k exists and can be found in linear time. We apply it to show, among others, the following: Every planar hamiltonian graph G = ( V ( G ) , E ( G ) ) with minimum degree delta >= 4 has a cycle of length k for every k is an element of { L divide V ( G ) divide 2 <SIC> RIGHT FLOOR , horizontal ellipsis , left ceiling divide V ( G ) divide 2 right ceiling + 3 } with 3 <= k <= divide V ( G ) divide . Every 3-connected planar hamiltonian graph G with delta >= 4 and divide V ( G ) divide >= 8 even has a cycle of length divide V ( G ) divide 2 - 1 or divide V ( G ) divide 2 - 2. 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.
Year
DOI
Venue
2019
10.1002/jgt.22712
JOURNAL OF GRAPH THEORY
Keywords
DocType
Volume
cycles in planar hamiltonian graphs, subtree sums
Journal
98
Issue
ISSN
Citations 
3
0364-9024
0
PageRank 
References 
Authors
0.34
8
1
Name
Order
Citations
PageRank
On-Hei Solomon Lo102.03