Graphs where every maximal path is maximum
type: Item
instance of: scholarly article
title: Graphs where every maximal path is maximum
zbMATH Open document ID: 0860.05062
author: Michael Tarsi
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-04-21T00:00:00Z
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.
reviewed by: Andreas Huck
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 934818
zbMATH Keywords: characterization
zbMATH Keywords: Hamiltonian path
zbMATH Keywords: path of maximal length
MaRDI profile type: Publication
full work available at URL: jctb.1996.0048
OpenAlex ID: W2094475111
DOI: 10.1006/JCTB.1996.0048
description: scientific article; zbMATH DE number 934818