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

Lattice graphs with non-concurrent longest cycles

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

(1) Department of Mathematics, Shah Abdul Latif University, Khairpur, 66020, Sindh, Pakistan
(2) Fakultät für Mathematik, Technische Universität Dortmund, Vogelpothsweg 87, 44227, Dortmund, Germany
(3) Fakultät für Mathematik, Technische Universität Dortmund, Vogelpothsweg 87, 44227, 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