Hamiltonian threshold for strong products of graphs |
| |
| Authors: | Daniel Král' Ladislav Stacho |
| |
| Institution: | 1. Institute for Theoretical Computer Science (ITI), Charles University, Malostranské Náměstí 25, 118 00 Prague, Czech Republic;2. Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby BC, Canada |
| |
| Abstract: | We prove that the strong product of any at least  non‐trivial connected graphs of maximum degree at most Δ is pancyclic. The obtained result is asymptotically best possible since the strong product of ?(ln 2)D? stars K1,D is not even hamiltonian. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 314–328, 2008 |
| |
| Keywords: | Hamilton cycle strong graph product |
|
|
