A short proof of Fleischner's theorem

DOI10.1016/J.DISC.2009.06.024MaRDI QIDQ1045203zbMATH OpenOpenAlexFDO

Authors Agelos Georgakopoulos

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Fleischner's theoremHamilton cycle

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We introduce a variant of the cover time of a graph, called cover cost, in which the cost of a step is proportional to the number of yet uncovered vertices. It turns out that cover cost is more tractable than cover time; we provide an $O(n^4)$ algorithm for its computation, as well as some explicit formulae. The two values are not very far from each other, and so cover cost might be a useful tool in the study of cover time.

Recommendations

• A short proof of the versatile version of Fleischner's theorem
• A new proof of the theorem by Fleischner
• Publication:3491596
• A SHORT PROOF OF A THEOREM OF PFITZNER
• Publication:3485174
• A short proof of Klee's theorem
• scientific article; zbMATH DE number 3960534
• A short proof of Levinson's theorem
• A short proof of the Schröder-Simpson theorem
• scientific article; zbMATH DE number 5552458

Cites work

• A new proof of the theorem by Fleischner
• Hamiltonian Paths in Squares of Infinite Locally Finite Blocks
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Infinite Hamilton cycles in squares of locally finite graphs
• Infinite highly connected planar graphs of large girth
• On spanning subgraphs of a connected bridgeless graph and their application to DT-graphs
• The Cycle Space of an Infinite Graph
• The square of every two-connected graph is Hamiltonian

Cited in

(13)

• A best possible result for the square of a 2-block to be Hamiltonian
• Single-source three-disjoint path covers in cubes of connected graphs
• Disjoint path covers in cubes of connected graphs
• Infinite Hamilton cycles in squares of locally finite graphs
• A short proof of the versatile version of Fleischner's theorem
• A short proof of jacobian hypothesis implies flatness
• Spanning connectivity of the power of a graph and Hamilton-connected index of a graph
• The most general structure of graphs with Hamiltonian or Hamiltonian connected square
• Dirac's condition for completely independent spanning trees
• Hamilton powers of Eulerian digraphs
• Simple (invited talk)
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• A very short proof of Dixon's theorem

This page was built for publication: A short proof of Fleischner's theorem

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