Find subtrees of specified weight and cycles of specified length in linear time
Journal of Graph Theory · 2021-11 · 98 (3) · 531-552
DOI: 10.1002/jgt.22712 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 20.07.2021. Verfasst von On‐Hei Solomon Lo. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 25 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Lo, O. S. (2021). Find subtrees of specified weight and cycles of specified length in linear time. Journal of Graph Theory, 98(3), 531-552. https://doi.org/10.1002/jgt.22712
Vancouver
Lo OS. Find subtrees of specified weight and cycles of specified length in linear time. Journal of Graph Theory. 2021;98(3):531-552. doi:10.1002/jgt.22712
BibTeX
@article{Lo2021,
author = {Lo, On‐Hei Solomon},
title = {Find subtrees of specified weight and cycles of specified length in linear time},
journal = {Journal of Graph Theory},
year = {2021},
volume = {98},
number = {3},
pages = {531--552},
doi = {10.1002/jgt.22712}
}
EUVIMED