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. | Turk J Math (2016) 40: 21 – 31 ¨ ITAK ˙ c TUB ⃝ Turkish Journal of Mathematics doi: Research Article Highly non-concurrent longest paths in lattices 1 Yasir BASHIR1,∗, Faisal NADEEM2 , Ayesha SHABBIR3,4 Faculty of Mathematics, COMSATS Institute of Information Technology Wah Campus, Wah Cantt, Pakistan 2 Faculty of Mathematics, COMSATS Institute of Information Technology Lahore Campus, Lahore, Pakistan 3 Abdus Salam School of Mathematical Sciences, GC University, 68-B, New Muslim Town, Lahore, Pakistan 4 University College of Engineering, Sciences and Technology, Lahore Leads University, Lahore, Pakistan Received: • Accepted/Published Online: • Final Version: 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. Key words: lattice graph, longest path, torus, M¨ obius strip, Klein bottle 1. Introduction A graph is called hypohamiltonian if it is not hamiltonian but deleting any vertex gives a hamiltonian graph. The existence of hypohamiltonian graphs was the motivation of the following problem: “Do there exist graphs in which every vertex is missed by some longest path?”, which was raised by Gallai in 1966 [5]. This problem received a positive answer in 1969, by a planar example with 25 vertices found by Walther [15]. Later a graph with only 12 vertices was found by Voss and Walther [16] and Zamfirescu [20], independently. In [20], it was conjectured that the order 12 is the smallest possible for such a graph. Recently, by using computers, Brinkmann and Van Cleemput proved that it is indeed minimal (see reference [5] in [12]). [12] is a survey that includes results regarding
