Highly non-concurrent longest paths in lattices

Authors

YASIR BASHIR
FAISAL NADEEM
AYESHA SHABBIR

Abstract

In this paper we consider graphs in which any pair of vertices is missed by some longest path. We are proving the existence of such graphs in the infinite triangular, square and hexagonal lattices in the plane. Moreover, we extend our investigation to lattices on several surfaces such as the torus, the M\"obius strip and the Klein bottle.

DOI

10.3906/mat-1502-32

Keywords

lattice graph, longest path, torus, M\"obius strip, Klein bottle

First Page

21

Last Page

31

Recommended Citation

BASHIR, YASIR; NADEEM, FAISAL; and SHABBIR, AYESHA (2016) "Highly non-concurrent longest paths in lattices," Turkish Journal of Mathematics: Vol. 40: No. 1, Article 2. https://doi.org/10.3906/mat-1502-32
Available at: https://journals.tubitak.gov.tr/math/vol40/iss1/2