Pancyclicity of strong products of graphs (Q1889847)

A graph with \(n\) vertices is pancyclic if it contains a cycle of length \(s\) for all \(s\), \(3\leq s\leq n\). In particular, a pancyclic graph is Hamiltonian. The {strong product} of \(k\) graphs \(G_1=(V_1,E_1),\dots, G_k=(V_k,E_k)\) is the graph \(G_1\times\cdots\times G_k\) with \(V_1\times\cdots \times V_k\) as set of vertices and two vertices \((u_1,\dots,u_k)\) and \((v_1,\dots,v_k)\) adjacent if, for all \(i\), \(1\leq i\leq k\), either \(u_i=v_i\) or \(u_iv_i\in E_i\). As usual, \(G^k\) denotes the strong product of \(k\) copies of \(G\). The paper gives sufficient conditions on \(k\) and the maximum degree \(\Delta\) of the graphs \(G_1,\dots, G_k\) for \(G_1\times \cdots \times G_k\) to be pancyclic (in particular for \(G^k\) to be Hamiltonian). To be precise, the following two theorems are shown: (1) If \(G_1,\dots, G_k\) are connected graphs of maximum degree at most \(\Delta\), \(\Delta>32\), and \(k\geq\lfloor (253/320)\Delta\rfloor +\lceil \log_2\Delta \rceil +3\), then \(G_1\times\cdots\times G_k\) is pancyclic. (2) Let \(\Delta>32\). For each \(c>\ln (25/12)+1/64\) there exists \(c'\) such that if \(k\geq \lfloor c\Delta \rfloor+\lceil \log_2\Delta\rceil+c'\), then the strong product of any \(k\) connected graphs of maximum degree at most \(\Delta\) is pancyclic. For a given graph \(G\), let \(h(G)\) be the smallest value of \(k\) such that \(G^k\) is Hamiltonian. The existence of \(h(G)\) was proved in [\textit{J. C. Bermond, A. Germa} and \textit{M. C. Heydemann}, Can. Math. Bull. 22, 305--309 (1979; Zbl 0423.05027)]. Now, let \(h(\Delta)\) be the maximum of the values \(h(G)\) with \(G\) a graph of maximum degree \(\leq \Delta\). The concluding remarks of the paper are devoted to discuss the values of \(h(\Delta)\). The authors conjecture that \(\lim_{\Delta\to\infty}(h(\Delta)/\Delta)=\ln 2\).