A lower bound for the optimal crossing-free Hamiltonian cycle problem
type: Item
instance of: scholarly article
title: A lower bound for the optimal crossing-free Hamiltonian cycle problem
zbMATH Open document ID: 0623.05037
DOI: 10.1007/BF02187887
author: Ryan Hayward
published in: Discrete \& Computational Geometry
publication date: 1987-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131026
review text: Consider a drawing in the plane of \(K_ n\), the complete graph on n vertices. If all edges are restricted to be straight line segments, the drawing is called rectilinear. Consider a Hamiltonian cycle in a drawing of \(K_ n\). If no pair of the edges of the cycle cross, it is called a crossing-free Hamiltonian cycle (cfhc). Let \(\Phi\) (n) represent the maximum number of cfhc's of any drawing of \(K_ n\), and \(\Phi\) (n) the maximum number of cfhc's of any rectilinear drawing of \(K_ n\). The problem of determining \(\Phi\) (n) and \({\bar \Phi}\)(n), and determining which drawings have this many cfhc's, is known as the optimal cfhc problem. We present a brief survey of recent work on this problem, and then, employing a recursive counting argument based on computer enumeration, we establish a substantially improved lower bound for \(\Phi\) (n) and \({\bar \Phi}\)(n). In particular, it is shown that \({\bar \Phi}\)(n) is at least \(k\times 3.2684^ n\). We conjecture that both \(\Phi\) (n) and \({\bar \Phi}\)(n) are at most \(c\times 4.5^ n\).
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05-04
zbMATH DE Number: 4010559
zbMATH Keywords: complete graph
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: rectilinear drawing
MaRDI profile type: Publication
cites work: Q3855221
cites work: Crossing-Free Subgraphs
cites work: Crossing Number Problems
cites work: Optimal crossing-free Hamiltonian circuit drawings of \(K_n\)
Recommended article: A lower bound on the number of hamiltonian cycles
Recommended article: Q3974694
Recommended article: A lower bound on the number of Hamiltonian cycles through a prescribed edge in a crossed cube
Recommended article: An extremal problem for cycles in hamiltonian graphs
Recommended article: A lower bound on the Hamiltonian path completion number of a line graph
Recommended article: A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
Recommended article: An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
Recommended article: A lower bound for the shortest Hamiltonean path in directed graphs
Recommended article: On the complexity of hamiltonian path and cycle problems in certain classes of digraphs
description: scientific article; zbMATH DE number 4010559