A Planar Lattice Graph, with Empty Intersection of All Longest Path
Volume 3, Issue 1, June 2019, Pages: 6-8
Received: Mar. 5, 2019;
Accepted: Jun. 12, 2019;
Published: Jun. 26, 2019
Views 301 Downloads 50
Abdul Naeem Kalhoro, Department of Mathematics, Faculty of Physical Sciences, Shah Abdul Latif University, Khairpur, Pakistan
Ali Dino Jumani, Department of Mathematics, Faculty of Physical Sciences, Shah Abdul Latif University, Khairpur, Pakistan
Follow on us
Tibor Gallai in 1966 elevated the declaration about the existence of graphs with the property that every vertex is missed by some longest path. This property will be called Gallai’s property. First answer back by H. Walther, who introduced a planar graph on 25 vertices satisfying Gallai’s property, and various authors worked on that property, after examples of such graphs were found while examining such n-dimensional Ln graphs with the property that every longest Paths have empty intersection, can be embeddable in IRn, Some in equilateral triangular lattice T, Square lattice L2, hexagonal lattice H, also on the torus, Mobius strip, and the Klein bottle but no hypo-Hamiltonian graphs are embeddable in the planar square lattice. In this paper we present a graph embeddable into Cubic lattices L3, such that graphs can also occur as sub graphs of the cubic lattices, and enjoying the property that every vertex is missed by some longest path. Here research has also significance in applications. What if several processing units are interlinked as parts of a lattice network. Some of them developing a chain of maximal length are used to solve a certain task. To get a self-stable fault-tolerant system, it is indispensable that in case of failure of any unit or link, another chain of same length, not containing the faulty unit or link, can exchange the chain originally used. This is exactly the case investigated here. We denote by Ln the n-dimensional cubic lattice in IRn.
Longest Paths, Longest Cycles, Lattice Graphs, Cubic Lattices, Gallai's Property
To cite this article
Abdul Naeem Kalhoro,
Ali Dino Jumani,
A Planar Lattice Graph, with Empty Intersection of All Longest Path, Engineering Mathematics.
Vol. 3, No. 1,
2019, pp. 6-8.
Copyright © 2019 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/
) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
T. Gallai, Problem 4, in: Theory of Graphs, Proc. Tihany 1966 (eds.: P. Erd¨os & G. Katona), Academic Press, New York, 1968, p. 362.
H. Walther, Uber die Nichtexistenz eines Knotenpunktes, durch den alle l¨angsten Wege¨ eines Graphen gehen, J. Combin. Theory 6 (1969) 1–6.
T. Zamfirescu, A two-connected planar graph without concurrent longest paths, J. Combin. Theory, Ser. B 13 (1972) 116–121.
B. Grunbaum¨, Vertices missed by longest paths or circuits, J. Combin. Theory, Ser. A 17 (1974) 31–38.
B. Menke, Ch. Zamfirescu, T. Zamfirescu, Intersection of longest cycles in grid graphs, J. Graph Theory 25 (1997) 37–52.
F. Nadeem, A. Shabbir, T. Zamfirescu, Planar lattice graphs with Gallai’s property, Graphs Combin., DOI: 10.1007/s00373-012-1177-8.
S. Klavˇzar, M. Petkovˇsek, Graphs with non-empty intersection of longest paths, Ars Combin. 29 (1990) 13–52.
B. Menke, Longest cycles in grid graphs, Studia Math. Hung. 36 (2000) 201–230.
A. D. Jumani and T. Zamfirescu, “On longest paths in triangular lattice graphs,” vol. 89, pp. 269–273, 2012.
A. Shabbir, “Fault-tolerant designs in lattice networks on the klein bottle,” vol. 2, no. 2, pp. 99–109, 2014.
Y. Bashir, F. Nadeem, and A. Shabbir, “Highly non-concurrent longest paths in lattices,” vol. 40, pp. 21–31, 2016.
H. Walther, H.-J. Voss, Uber Kreise in Graphen¨, VEB Deutscher Verlag der Wissenschaften, Berlin, 1974.
T. Zamfirescu, On longest paths and circuits in graphs, Math. Scand. 38 (1976) 211–239
W. Schmitz, Uber l¨angste Wege und Kreise in Graphen,¨ Rend. Sem. Mat. Univ. Padova 53 (1975) 97–103.
Yasir Bashir, Tudor Zamfirescu, Lattice graphs with Gallai's property, Bull. Math. Soc. Sci.