Maximum strong diameter of the strong product of complete multipartite graph and path

Strong product graphs are well-suited for modeling interconnected networks in parallel computing systems. In such networks, the strong diameter is defined as the maximum strong distance between any two vertices, which serves as a key measure of transmission efficiency. A smaller strong diameter corresponds to higher efficiency and lower latency. Optimizing this parameter can significantly enhance information transmission speed. In this paper, we form the strong product network $K_{m_1,m_2,\dots ,m_k}\otimes P_n$ by taking the complete multipartite graph $K_{m_1,m_2,\dots ,m_k}|\{m_i\ge 1,i=1,2,\dots ,k\}$ and the path $P_n$ as the subgraphs. On this basis, we summarize and apply different strong orientation methods to investigate its maximum strong diameter. Specifically, we investigate the maximum strong diameter of $K_{m_1,m_2,\dots ,m_k}\otimes P_n$, establishing its exact value and bounds for the cases in which $K_{m_1,m_2,\dots ,m_k}|\{m_i\ge 1,i=1,2,\dots ,k\}$ does or does not admit a Hamiltonian cycle. In addition, a new algorithm is proposed to find the maximum strong diameter of $K_{m_1,m_2,\dots ,m_k}\otimes P_n$. Through simulation experiments, we find that the high-dimensional strong product network $K_{m_1,m_2,\dots ,m_k}\otimes P_n$ demonstrates superior information transfer efficiency when the underlying graph $K_{m_1,m_2,\dots ,m_k}|\{m_i\ge 1,i=1,2,\dots ,k\}$ lacks a Hamiltonian cycle.