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

DOI10.1002/JGT.22712zbMATH Open1522.05241arXiv1902.06484OpenAlexW3199315121MaRDI QIDQ6056757FDOQ6056757

On-Hei S. Lo

Publication date: 4 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We apply the Euler tour technique to find subtrees of specified weight as follows. Let $k,g,N_1,N_{2}inmathbbN$ such that $1leqkleq{N}_2$, $g+h>2$ and $2k-4g-h+3leq{N}_{2}leq2k+g+h-2$, where $h:=2N_1-N_2$. Let $T$ be a tree of $N_1$ vertices and let $c:V(T)ightarrowmathbbN$ be vertex weights such that $c(T):=su{m}_{vinV(T)}c(v)=N_2$ and $c(v)leqk$ for all $vinV(T)$. We prove that a subtree $S$ of $T$ of weight $k-g+1leqc(S)leqk$ exists and can be found in linear time. We apply it to show, among others, the following: (i) Every planar hamiltonian graph $G=(V(G),E(G))$ with minimum degree $deltageq4$ has a cycle of length $k$ for every $kinlfloorfrac|V(G)|2floor,dots,lceilfrac|V(G)|2ceil+3$ with $3leqkleq|V(G)|$. (ii) Every $3$-connected planar hamiltonian graph $G$ with $deltageq4$ and $|V(G)|geq8$ 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 of the graph is given. This work was partially motivated by conjectures of Bondy and Malkevitch on cycle spectra of 4-connected planar graphs.

Full work available at URL: https://arxiv.org/abs/1902.06484

Recommendations

• Finding cycles and trees in sublinear time
• A linear time algorithm for finding an optimal degree-bounded subtree of an edge-weighted tree
• Algorithms and Computation
• Computing minimum cycle bases in weighted partial 2-trees in linear time
• Computing minimum cycle bases in weighted partial 2-trees in linear time
• scientific article; zbMATH DE number 3959487
• A linear time and space algorithm for finding isomorphic subtrees of a binary tree
• An optimal algorithm for computing all subtree repeats in trees
• An optimal algorithm for computing all subtree repeats in trees
• scientific article; zbMATH DE number 2080269

zbMATH Keywords

cycles in planar Hamiltonian graphssubtree sums

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• A linear algorithm for embedding planar graphs using PQ-trees
• Color-coding
• Finding and counting given length cycles
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• A Theorem on Planar Graphs
• 4-connected projective planar graphs are Hamiltonian
• A theorem on paths in planar graphs
• Title not available (Why is that?)
• Choosability and edge choosability of planar graphs without five cycles
• Planar graphs without cycles of specific lengths
• Finding large cycles in Hamiltonian graphs
• Long cycles in 4-connected planar graphs
• Cycles in 4-connected planar graphs
• On Hamilton cycles in certain planar graphs
• On planar graphs arbitrarily decomposable into closed trails
• Some 4-valent, 3-connected, planar, almost pancyclic graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Distribution of subtree sums
• Cycle spectra of contraction-critically 4-connected planar graphs
• Cycles in 3-connected claw-free planar graphs and 4-connected planar graphs without 4-cycles

This page was built for publication: Find subtrees of specified weight and cycles of specified length in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6056757)