Hostname: page-component-848d4c4894-ttngx Total loading time: 0 Render date: 2024-05-01T22:05:24.072Z Has data issue: false hasContentIssue false
  • English
  • Français

Hamiltonian Cycles in Strong Products of Graphs

Published online by Cambridge University Press:  20 November 2018

J. C. Bermond ,
A. Germa  and
M. C. Heydemann
J. C. Bermond
Affiliation:
Université Paris-Sud, Informatique, Bâtiment 490, 91405. Orsay, France
A. Germa
Affiliation:
Université Paris-Sud, Informatique, Bâtiment 490, 91405. Orsay, France
M. C. Heydemann
Affiliation:
Université Paris-Sud, Informatique, Bâtiment 490, 91405. Orsay, France
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Abstract. Let denote the graph (k times) where is the strong product of the two graphs G and H. In this paper we prove the conjecture of J. Zaks [3]: For every connected graph G with at least two vertices there exists an integer k = k(G) for which the graph is hamiltonian.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 22 , Issue 3 , 01 September 1979 , pp. 305 - 309
Copyright
Copyright © Canadian Mathematical Society 1979

References

1. Berge, C. Graphs and Hypergraphs, North-Holland. Amsterdam 1973.Google Scholar
2. Rosenfeld, M. and Barnette, D., Hamiltonian Circuits in Certain Prisms, Discrete Math. 5, 1973, 389-394.Google Scholar
3. Zaks, J.. Hamiltonian cycles in products of graphs, Canadian Math. Bull. vol. 17 (5), 1975, 763-765.Google Scholar