| Peer-Reviewed

A Planar Lattice Graph, with Empty Intersection of All Longest Path

Received: 5 March 2019     Accepted: 12 June 2019     Published: 26 June 2019
Views:       Downloads:
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.

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), 2019. Published by Science Publishing Group

Keywords

Longest Paths, Longest Cycles, Lattice Graphs, Cubic Lattices, Gallai's Property

References
[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.
Cite This Article
  • 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

    Copy | Download

    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

    Copy | Download

    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

    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}
    }
    

    Copy | Download

  • 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  - 

    Copy | Download

Author Information
  • Department of Mathematics, Faculty of Physical Sciences, Shah Abdul Latif University, Khairpur, Pakistan

  • Department of Mathematics, Faculty of Physical Sciences, Shah Abdul Latif University, Khairpur, Pakistan

  • Sections