Hamilton cycles in strong products of graphs

descriptionPublicationkeyboard_double_arrow_right Article 15 Feb 2005 English Publisher:WileyJournal:Journal of Graph Theory, volume 48, pages 299-321 (issn: 0364-9024, eissn: 1097-0118,

Copyright policy )

Authors: Daniel Král; Jana Maxová; Robert Sámal; Pavel Podbrdský;

doi: 10.1002/jgt.20058

Hamilton cycles in strong products of graphs

- Summary
- Subjects
- Metrics

Abstract

AbstractWe prove that the strong product of any n connected graphs of maximum degree at most n contains a Hamilton cycle. In particular, GΔ(G) is hamiltonian for each connected graph G, which answers in affirmative a conjecture of Bermond, Germa, and Heydemann. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 299–321, 2005

Related Organizations

Charles University
Czech Republic

Keywords

Eulerian and Hamiltonian graphs, graph powers, Hamilton cycles

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	4
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average