Highly nonconcurrent longest paths and cycles in lattices

We investigate here the connected graphs with the property that any pair of vertices are missed by some longest paths (or cycles), embeddable in n-dimensional lattices Ln where L denotes the set of integers.

Highly nonconcurrent longest paths and cycles in lattices

We investigate here the connected graphs with the property that any pair of vertices are missed by some longest paths (or cycles), embeddable in n-dimensional lattices Ln where L denotes the set of integers.

___

  • Bashir Y, Zamfirescu T. Lattice graphs with Gallai’s property. Bull Math Soc Sci Math Roumanie 2013, 104: 65–71. Gallai T. Problem 4. In: Erd¨ os P, Katona G, editors. Theory of Graphs, Proc. Tihany 1966, New York, NY, USA: Academic Press, 1968, p. 362.
  • Menke B, Zamfirescu Ch, Zamfirescu T. Intersection of longest cycles in grid graphs. J Graph Theory 1997; 25: 37–
  • Menke B. Longest cycles in grid graphs. Studia Math Hung 2000; 36: 201–230.
  • Shabbir A, Zamfirescu T. Highly non-concurrent longest cycles in lattice graphs. Discrete Math DOI: 1016/j.disc.2012.03.015.
  • Walther H. ¨ Uber die Nichtexistenz eines Knotenpunktes, durch den alle l¨ angsten Wege eines Graphen gehen. J Comb Theory 1969; 6: 1–6 (in German).
  • Zamfirescu T. A two-connected planar graph without concurrent longest paths. J Combin Theory B 1972; 13: 116–121.
  • Zamfirescu T. On longest paths and circuits in graphs. Math Scand 1976; 38: 211–239.
  • Zamfirescu T. Intersecting longest paths or cycles: A short survey. Analele Univ Craiova, Seria Mat Inf 2001; 28: 1–