On k-distant Hamiltonian Walks of the Strong Product Graphs

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 k-distant Hamiltonian walk indicates a generalization of the Hamiltonian cycle, and the k-distant Hamiltonian walk in the graph demonstrates a cyclic sequence of all its vertices, where the distance between two consecutive vertices is k. In the design of wireless sensor networks, the k-distant Hamiltonian walk plays an important role. In this paper, sufficient conditions are determined for the existence of k-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 k-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.