On k -distant Hamiltonian Walks of the Strong Product Graphs
Haoran Yin, Feng Li, Zhixuan Zhang · Parallel Processing Letters · 2025
The strong product serves as an essential method to build parallel processing network models utilizing a number of small graphs. The network models constructed through the strong product incorporate these small graphs as subgraphs and preserve many of the advantageous properties of the factor graphs. The [Formula: see text]-distant Hamiltonian walk indicates a generalization of the Hamiltonian cycle, and the [Formula: see text]-distant Hamiltonian walk in the graph demonstrates a cyclic sequence of all its vertices, where the distance between two consecutive vertices is [Formula: see text]. In the design of wireless sensor networks, the [Formula: see text]-distant Hamiltonian walk plays an important role. In this paper, sufficient conditions are determined for the existence of [Formula: see text]-distant Hamiltonian walks in the strong product of simple, connected, undirected graphs. These conditions are derived on the basis of the connectivity, degree, and specific edge connectivity of the graph. The existence of [Formula: see text]-distant Hamiltonian walks is tested by exploring the strong product topology, with relevant theorems and examples provided, and corresponding algorithms given to verify the applicability and effectiveness of the parallel network model proposed in this paper.