In this paper we deal with hamiltonicity in planar cubic graphs G having a facial 2–factor 𝒬 via (quasi) spanning trees of faces in G/𝒬 and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if Barnette’s Conjecture is false, then hamiltonicity in 3–connected planar cubic bipartite graphs is an NP-complete problem.

Anderson et al. [{\it Amer. Math. Monthly}, 96 (1989), pp. 481--493] studied a combinatorial game on an infinite path that is started with n disks at a vertex and ends with the disks spread between $k=\lfloor n/2 \rfloor$ vertices to the left and to the right of the initial vertex. They showed that the number of steps the game takes to converge to the final configuration is $ck^2+o(k^2)$ for some constant c. We generalize this game to the case of an infinite rooted tree, where each vertex has degree $d+1$ and where the earlier game corresponds to the case $d=1$. We determine the final configuration when the game is started with n disks at the root and show that in this final configuration all disks are at depth at most $k=\Theta(\log_d n)$ for $d\geq 2$. We also show that the number of steps that the game takes to converge to the final configuration in this case is at most $O(k(1+ \log_d k))$, so that the convergence is faster than what it was for the case $d=1$. We generalize the game to the case where the vertices at depth i in the tree have $d_i\geq 2$ children, where the $d_i$ are not necessarily the same, and show that the convergence time in this case is at most $O(k^{1.5} + k \log_{d_{\min}} d_{\max})$, where $d_{\min}$ and $d_{\max}$ are the smallest and largest $d_i$, respectively.

We consider the problem of finding long paths and cycles in Hamiltonian graphs. The focus of our work is on sparse graphs, e.g., cubic graphs, that satisfy some property known to hold for Hamiltonian graphs, e.g., k-cyclability. We first consider the problem of finding long cycles in 3-connected cubic graphs whose edges have weights $w_i\geq 0$. We find cycles of weight at least ${(\sum w_i^a)}^{\frac{1}{a}}$ for $a=\log_2 3$. Based on this result, we develop an algorithm for finding a cycle of length at least $m^{(\log_3 2)/2}\approx m^{0.315}$ in 3-cyclable graphs with vertices of degree at most 3 and with m edges. As a corollary of this result, for arbitrary graphs with vertices of degree at most 3 that have a cycle of length l (or, more generally, a 3-cyclable minor with degrees at most 3 and with l edges), we find a cycle of length at least $l^{(\log_3 2)/2}$. We consider the graph property of 1-toughness that is common to Hamiltonian graphs and 3-connected cubic graphs, and we try to determine if 1-toughness implies the existence of long cycles. We show that 2-connectivity and 1-toughness, for constant degree graphs, may give cycles that are only of logarithmic length. However, we exhibit a class of 3-connected 1-tough graphs with degrees up to 6, where we can find cycles of length at least ${m}^{\log_3 2}/2$.

Article Finding long paths and cycles in sparse Hamiltonian graphs Share on Authors: Tomas Feder View Profile , Rajeev Motwani Department of Computer Science, Stanford University, CA Department of Computer Science, Stanford University, CAView Profile , Carlos Subi View Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 524–529https://doi.org/10.1145/335305.335368Online:01 May 2000Publication History 9citation694DownloadsMetricsTotal Citations9Total Downloads694Last 12 Months16Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access