Graphs where every maximal path is maximum

DOI10.1006/JCTB.1996.0048MaRDI QIDQ1924151zbMATH OpenOpenAlexFDO

Authors Michael Tarsi

Publication date 21 April 1997

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.0048

zbMATH Keywords

characterizationHamiltonian pathpath of maximal length

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Structural characterization of families of graphs (05C75)

Review text

In 1974, C. Thomassen gave a characterization of all graphs in which each path is contained in a Hamiltonian path. Such graphs are of interest since they admit greedy algorithms for constructing Hamiltonian paths. For graphs without a Hamiltonian path, it is natural to ask whether each path is contained in a path of maximal length. In the present paper the author characterizes all connected graphs without a Hamiltonian path having this property.

Recommendations

• Graphs maximal with respect to absence of hamiltonian paths
• Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests
• Scenic graphs. I: Traceable graphs
• scientific article; zbMATH DE number 1334643

Cited in

(7)

• Scenic graphs. I: Traceable graphs
• Lower bounds on the odds against tree spectral sets
• Non‐path spectrum sets
• Graphs maximal with respect to absence of hamiltonian paths
• scientific article; zbMATH DE number 1334643 (Why is no real title available?)
• Path spectra for trees
• Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests

This page was built for publication: Graphs where every maximal path is maximum

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