EUVIMEDEUVIMED entdecken
Crossref

Find subtrees of specified weight and cycles of specified length in linear time

On‐Hei Solomon Lo

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →