×

Longest paths joining given vertices in a graph. (English) Zbl 0613.05033

It is shown that results of S. C. Locke [Thesis (1981)] and H. Enomoto [Longest paths and large cycles in finite graphs, J. Graph Theory 8, 287-301 (1984; Zbl 0544.05044)] can be strengthened for certain restricted classes of graphs.

MSC:

05C38 Paths and cycles
05C35 Extremal problems in graph theory

Keywords:

longest path

Citations:

Zbl 0544.05044
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. A. Bondy, Longest paths and cycles in graphs of high degree, University of Waterloo Preprint CORE, 80–76.
[2] J. A. Bondy andB. Jackson, Long paths between specified vertices of a block, to appear. · Zbl 0581.05033
[3] H. Enomoto, Long paths and large cycles in finite graphs, Journal of Graph Theory 8 (1984), 287–301. · Zbl 0544.05044 · doi:10.1002/jgt.3190080209
[4] P. Erdös andT. Gallai, On maximal paths and circuits in graphs, Acta Math. Acad. Sci. Hung. 10 (1959), 337–356. · Zbl 0090.39401 · doi:10.1007/BF02024498
[5] J. Fournier andP. Fraisse, On a conjecture of Bondy, J. of Combinatorial Theory Ser. B 38 (1985). · Zbl 0576.05035
[6] H. A. Jung, Longest circuits in 3-connected graphs, Coll. Math. Soc. J. Bolyai, 37. Finite and infinite sets, Eger (1981), 403–438.
[7] S. C. Locke, Ph. D. Thesis, University of Waterloo (1981).
[8] C. St. J. A. Nash-Williams, Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics (pres, to R. Rado), Academic Press London (1971), 157–183. · Zbl 0223.05123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.