Premium
Hamiltonian threshold for strong products of graphs
Author(s) -
Král' Daniel,
Stacho Ladislav
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20314
Subject(s) - mathematics , combinatorics , hamiltonian (control theory) , graph , product (mathematics) , discrete mathematics , geometry , mathematical optimization
We prove that the strong product of any at least ${({\rm ln}}\, {2})\Delta+{O}(\sqrt{\Delta})$ 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 K 1, D is not even hamiltonian. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 314–328, 2008