Rendiconti del Seminario Matematico della Università di Padova

Full-Text PDF (308 KB) | Metadata | Table of Contents | RSMUP summary
Volume 132, 2014, pp. 75–82
DOI: 10.4171/RSMUP/132-6

Published online: 2014-11-04

Lattice graphs with non-concurrent longest cycles

Ali Dino Jumani[1], Carol T. Zamfirescu[2] and Tudor I. Zamfirescu[3]

(1) Shah Abdul Latif University, Sindh, Pakistan
(2) Technische Universität Dortmund, Germany
(3) Technische Universität Dortmund, Germany

No hypohamiltonian graphs are embeddable in the planar square lattice. This lattice contains, however, graphs in which every vertex is missed by some longest cycle. In this paper we present graphs with this property, embeddable in various lattices, and of remarkably small order.

Keywords: Lattice graphs, longest cycles

Jumani Ali Dino, Zamfirescu Carol, Zamfirescu Tudor: Lattice graphs with non-concurrent longest cycles. Rend. Sem. Mat. Univ. Padova 132 (2014), 75-82. doi: 10.4171/RSMUP/132-6