Hamiltonian square-paths

DOI10.1006/JCTB.1996.0039MaRDI QIDQ1924142zbMATH OpenOpenAlexFDO

Authors Genghua Fan, H. A. Kierstead

Publication date 14 October 1996

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1996.0039

zbMATH Keywords

hamiltonian pathminimum degree

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

It is shown that if the minimum degree of a graph \(G\) on \(n\) vertices is at least \((2n-1)/3\) then \(G\) contains a subgraph that can be obtained from a hamiltonian path by adding all edges joining vertices of distance two on the path.

Recommendations

• The square of paths and cycles
• On minimum degree in Hamiltonian path graphs
• The Square of a Hamiltonian Cycle
• Forbidden subgraphs for a graph to have a Hamiltonian path square

Cited in

(28)

• Ore-type conditions implying 2-factors consisting of short cycles
• Proof of the Seymour conjecture for large graphs
• Square Hamiltonian cycles in graphs with maximal 4-cliques
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• Graphs containing every 2-factor
• The Wiener index of signed graphs
• Monochromatic square-cycle and square-path partitions
• Forbidden subgraphs for a graph to have a Hamiltonian path square
• Monochromatic cycle power partitions
• Stability for vertex cycle covers
• Large planar subgraphs in dense graphs
• On degree sequences forcing the square of a Hamilton cycle
• Embedding graphs having Ore-degree at most five
• On a degree sequence analogue of Pósa's conjecture
• scientific article; zbMATH DE number 6513170 (Why is no real title available?)
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• An Ore-type theorem on Hamiltonian square cycles
• On minimum degree in Hamiltonian path graphs
• Absolute differences along Hamiltonian paths
• Monochromatic bounded degree subgraph partitions
• Minimum Degrees for Powers of Paths and Cycles
• Dirac's condition for spanning Halin subgraphs
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Minimum degree conditions for powers of cycles and paths
• Characterizing forbidden pairs for Hamiltonian squares
• Spanning 3-colourable subgraphs of small bandwidth in dense graphs
• How to avoid using the regularity Lemma: Pósa's conjecture revisited

This page was built for publication: Hamiltonian square-paths

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