×

Hamilton cycles in prisms. (English) Zbl 1128.05034

Summary: The prism over a graph \(G\) is the Cartesian product \(G \square K_{2}\) of \(G\) with the complete graph \(K_2\). If \(G\) is Hamiltonian, then \(G \square K_2\) is also Hamiltonian but the converse does not hold in general. Having a Hamiltonian prism is shown to be an interesting relaxation of being Hamiltonian. In this article, we examine classical problems on Hamiltonicity of graphs in the context of having a Hamiltonian prism.

MSC:

05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, Graphs Combin 2 pp 1– (1986)
[2] Barnette, Canad J Math 18 pp 731– (1966) · Zbl 0141.21401 · doi:10.4153/CJM-1966-073-4
[3] Biebighauser, manuscript (2005)
[4] Bauer, Discrete Appl Math 99 pp 317– (2000)
[5] and , Graph Theory with Applications, Macmillan, London, and Elsevier, New York, 1976. · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[6] 2-connected claw-free graphs are prism-hamiltonian (in press).
[7] čada, Discrete Math 286 pp 45– (2004)
[8] Chvátal, Discrete Math 5 pp 215– (1973)
[9] Ellingham, Congr Numer 115 pp 55– (1996)
[10] Ellingham, J Graph Theory 33 pp 125– (2000)
[11] Fleischner, J Combin Theory B 16 pp 29– (1974)
[12] Fleischner, Ann Discrete Math 41 pp 141– (1989)
[13] Gao, J Combin Theory B 62 pp 259– (1994)
[14] Grünbaum, Bull AMS 76 pp 1131– (1970)
[15] Horák, Order 22 pp 73– (2005)
[16] Hamilton cycles in 7-connected line graphs, unpublished manuscript, 1989.
[17] Jackson, Australas J Combin 2 pp 135– (1990)
[18] Johnson, J Combin Theory A 105 pp 255– (2004)
[19] Král’, J Graph Theory 54 pp 209– (2007)
[20] Nash-Williams, Lect Note Math 185 pp 197– (1971)
[21] Paulraja, J Graph Theory 17 pp 161– (1993)
[22] Rosenfeld, Discrete Math 5 pp 389– (1973)
[23] Ryjáček, J Combin Theory B 70 pp 217– (1997)
[24] Thomassen, J Graph Theory 10 pp 309– (1986)
[25] and , On k-trestles in chordal polyhedral graphs, MATH-AL-15-2002, Technische Universität Dresden, 2002.
[26] Tutte, Trans. Amer Math Soc 82 pp 99– (1956)
[27] Win, Graphs Combin 5 pp 201– (1989)
[28] Zhan, Discrete Math 89 pp 89– (1991)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.