×
Jumani, Ali Dino; Zamfirescu, Carol T.; Zamfirescu, Tudor I.

Lattice graphs with non-concurrent longest cycles. (English) Zbl 1306.05114

Rend. Semin. Mat. Univ. Padova 132, 75-82 (2014).
Summary: No hypohamiltonian graphs are embeddable in the planar square lattice. This lattice contains, however, graphs in which every vertex is missed by some longest cycle. In this paper we present graphs with this property, embeddable in various lattices, and of remarkably small order.

MSC:

05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C12 Distance in graphs

Keywords:

lattice graphs; longest cycles
PDF BibTeX XML Cite
\textit{A. D. Jumani} et al., Rend. Semin. Mat. Univ. Padova 132, 75--82 (2014; Zbl 1306.05114)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Y. BASHIR - T. ZAMFIRESCU, Lattice graphs with Gallai’s property, Bull. Math. Soc. Sci. Math. Roumanie, 56 (2013), pp. 65-71. · Zbl 1349.05186
[2] Y.-C. CHEN - C.-H. TSAI - L.-H. HSU - J. J. M. TAN, On some super fault- tolerant Hamiltonian graphs, Appl. Math. Comput., 148 (2004), pp. 729-741. · Zbl 1032.05078
[3] T. GALLAI, Problem 4, in: Theory of Graphs Proc. Tihany 1966 (eds.: P. ErdoÈs & G. Katona), Academic Press, New York, 1968, p. 362.
[4] J. P. HAYES, A Graph Model for Fault-Tolerant Computing Systems, IEEE Trans. Comput., 25 (1976), pp. 875-884. · Zbl 0333.94015
[5] C.-N. HUNG - L.-H. HSU - T.-Y. SUNG, On the Construction of Combined k- Fault-Tolerant Hamiltonian Graphs, Networks, 37 (2001), pp. 165-170. · Zbl 0974.05051
[6] A. B. KEMPE, A Memoir on the Theory of Mathematical Form, Phil. Trans. Roy. Soc. Lond., 177 (1886), pp. 1-70.
[7] B. MENKE, Longest cycles in grid graphs, Studia Sci. Math. Hung., 36 (2000), pp. 201-230. · Zbl 0973.05048
[8] B. MENKE - CH. ZAMFIRESCU - T. ZAMFIRESCU, Intersections of longest cycles in grid graphs, J. Graph Theory, 25 (1997), pp. 37-52. · Zbl 0874.05032
[9] F. NADEEM - A. SHABBIR - T. ZAMFIRESCU, Planar lattice graphs with Gallai’s property, Graphs Combin., 29 (2013), pp. 1523-1529. · Zbl 1272.05095
[10] J.-H. PARK - H.-C. KIM - H.-S. LIM, Fault-hamiltonicity of hypercube-like interconnection networks, Proc. of IEEE International Parallel and Distrib- uted Processing Symposium IPDPS 2005, Denver, Apr. 2005.
[11] J.-H. PARK - H.-S. LIM - H.-C. KIM, Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Theoret. Comput. Sci., 377 (2007), pp. 170-180. · Zbl 1115.68116
[12] J. PETERSEN, Sur le theÂoreÁme de Tait, L’IntermeÂdiaire des MatheÂmaticiens, 5 (1898), pp. 225-227.
[13] A. SHABBIR - C . T. ZAMFIRESCU - T. I. ZAMFIRESCU, Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl., 1 (2013), pp. 56-76. · Zbl 1306.05121
[14] A. SHABBIR - T. ZAMFIRESCU, Fault-tolerant designs in triangular lattice networks, submitted. · Zbl 1461.05112
[15] H. WALTHER, UÈber die Nichtexistenz eines Knotenpunktes, durch den alle laÈngsten Wege eines Graphen gehen, J. Combin. Theory, 6 (1969), pp. 1-6. · Zbl 0184.27504
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.