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.
| Published in | Engineering Mathematics (Volume 3, Issue 1) |
| DOI | 10.11648/j.engmath.20190301.12 |
| Page(s) | 6-8 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2024. Published by Science Publishing Group |
Longest Paths, Longest Cycles, Lattice Graphs, Cubic Lattices, Gallai's Property
| [1] | T. Gallai, Problem 4, in: Theory of Graphs, Proc. Tihany 1966 (eds.: P. Erd¨os & G. Katona), Academic Press, New York, 1968, p. 362. |
| [2] | H. Walther, Uber die Nichtexistenz eines Knotenpunktes, durch den alle l¨angsten Wege¨ eines Graphen gehen, J. Combin. Theory 6 (1969) 1–6. |
| [3] | T. Zamfirescu, A two-connected planar graph without concurrent longest paths, J. Combin. Theory, Ser. B 13 (1972) 116–121. |
| [4] | B. Grunbaum¨, Vertices missed by longest paths or circuits, J. Combin. Theory, Ser. A 17 (1974) 31–38. |
| [5] | B. Menke, Ch. Zamfirescu, T. Zamfirescu, Intersection of longest cycles in grid graphs, J. Graph Theory 25 (1997) 37–52. |
| [6] | F. Nadeem, A. Shabbir, T. Zamfirescu, Planar lattice graphs with Gallai’s property, Graphs Combin., DOI: 10.1007/s00373-012-1177-8. |
| [7] | S. Klavˇzar, M. Petkovˇsek, Graphs with non-empty intersection of longest paths, Ars Combin. 29 (1990) 13–52. |
| [8] | B. Menke, Longest cycles in grid graphs, Studia Math. Hung. 36 (2000) 201–230. |
| [9] | A. D. Jumani and T. Zamfirescu, “On longest paths in triangular lattice graphs,” vol. 89, pp. 269–273, 2012. |
| [10] | A. Shabbir, “Fault-tolerant designs in lattice networks on the klein bottle,” vol. 2, no. 2, pp. 99–109, 2014. |
| [11] | Y. Bashir, F. Nadeem, and A. Shabbir, “Highly non-concurrent longest paths in lattices,” vol. 40, pp. 21–31, 2016. |
| [12] | H. Walther, H.-J. Voss, Uber Kreise in Graphen¨, VEB Deutscher Verlag der Wissenschaften, Berlin, 1974. |
| [13] | T. Zamfirescu, On longest paths and circuits in graphs, Math. Scand. 38 (1976) 211–239 |
| [14] | W. Schmitz, Uber l¨angste Wege und Kreise in Graphen,¨ Rend. Sem. Mat. Univ. Padova 53 (1975) 97–103. |
| [15] | Yasir Bashir, Tudor Zamfirescu, Lattice graphs with Gallai's property, Bull. Math. Soc. Sci. |
APA Style
Abdul Naeem Kalhoro, Ali Dino Jumani. (2019). A Planar Lattice Graph, with Empty Intersection of All Longest Path. Engineering Mathematics, 3(1), 6-8. https://doi.org/10.11648/j.engmath.20190301.12
ACS Style
Abdul Naeem Kalhoro; Ali Dino Jumani. A Planar Lattice Graph, with Empty Intersection of All Longest Path. Eng. Math. 2019, 3(1), 6-8. doi: 10.11648/j.engmath.20190301.12
AMA Style
Abdul Naeem Kalhoro, Ali Dino Jumani. A Planar Lattice Graph, with Empty Intersection of All Longest Path. Eng Math. 2019;3(1):6-8. doi: 10.11648/j.engmath.20190301.12
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.engmath.20190301.12,
author = {Abdul Naeem Kalhoro and Ali Dino Jumani},
title = {A Planar Lattice Graph, with Empty Intersection of All Longest Path},
journal = {Engineering Mathematics},
volume = {3},
number = {1},
pages = {6-8},
doi = {10.11648/j.engmath.20190301.12},
url = {https://doi.org/10.11648/j.engmath.20190301.12},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.engmath.20190301.12},
abstract = {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.},
year = {2019}
}
TY - JOUR T1 - A Planar Lattice Graph, with Empty Intersection of All Longest Path AU - Abdul Naeem Kalhoro AU - Ali Dino Jumani Y1 - 2019/06/26 PY - 2019 N1 - https://doi.org/10.11648/j.engmath.20190301.12 DO - 10.11648/j.engmath.20190301.12 T2 - Engineering Mathematics JF - Engineering Mathematics JO - Engineering Mathematics SP - 6 EP - 8 PB - Science Publishing Group SN - 2640-088X UR - https://doi.org/10.11648/j.engmath.20190301.12 AB - 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. VL - 3 IS - 1 ER -
Information
Email: