On longest cycles in grid graphs. (English) Zbl 0973.05048
The author studies the question if all longest paths of a connected graph contain a common vertex. First of all he presents a lattice graph with empty intersection of its longest cycles. Then he shows that all grid graphs form a family of graphs that have non-empty intersection of all longest paths (and all are non-Hamiltonian).
Reviewer: Ferdinand Gliviak (Bratislava)
MSC:
05C38 | Paths and cycles |