A short note on graphs with long Thomason chains

DOI10.1016/J.DISC.2021.112624MaRDI QIDQ2237207zbMATH OpenOpenAlexFDO

Authors Marcin Briański, Adam Szady

Publication date 27 October 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cubic graphHamiltonian cycleSmith's theoremThomason's algorithm

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We present a family of 3-connected cubic planar Hamiltonian graphs with an exponential number of steps required by Thomason's algorithm. The base of the exponent is approximately $\mathrm{1.1812...}$, which exceeds previous results in the area.

Recommendations

• Notes on Hamiltonian threshold and chain graphs
• Some Properties of Chain and Threshold Graphs
• Some notes on the threshold graphs
• On a conjecture of Thomassen concerning subgraphs of large girth
• scientific article; zbMATH DE number 1205987
• A characterization of long graphs of arbitrary rank
• Some results on graphs without long induced paths
• Some results on graphs without long induced paths
• \(k\)-long graphs
• k-long graphs

Cites work

• Analytic combinatorics
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Parameterized algorithms
• The complexity of finding a second Hamiltonian cycle in cubic graphs
• The complexity of Thomason's algorithm for finding a second Hamiltonian cycle
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs

Cited in

(3)

• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs
• The complexity of iterated reversible computation
• Another Hamiltonian cycle in bipartite Pfaffian graphs

This page was built for publication: A short note on graphs with long Thomason chains

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