@article{Zhang2026, 
author = {Ce Zhang and Feng Li},
title = {Maximum strong diameter of the strong product of complete multipartite graph and path},
year = {2026},
journal = {AIMS Mathematics},
volume = {11},
number = {4},
pages = {9260-9283},
keywords = {strong product graph, maximum strong diameter, complete multipartite graph, path},
url = {https://www.sciopen.com/article/10.3934/math.2026382},
doi = {10.3934/math.2026382},
abstract = {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            ,      …      ,              m        k              ⊗      P    n   by taking the complete multipartite graph        K                  m        1            ,              m        2            ,      …      ,              m        k                  |    {      m          i        ≥  1  ,  i  =  1  ,  2  ,  …  ,  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            ,      …      ,              m        k              ⊗      P    n  , establishing its exact value and bounds for the cases in which        K                  m        1            ,              m        2            ,      …      ,              m        k                  |    {      m          i        ≥  1  ,  i  =  1  ,  2  ,  …  ,  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            ,      …      ,              m        k              ⊗      P    n  . Through simulation experiments, we find that the high-dimensional strong product network        K                  m        1            ,              m        2            ,      …      ,              m        k              ⊗      P    n   demonstrates superior information transfer efficiency when the underlying graph        K                  m        1            ,              m        2            ,      …      ,              m        k                  |    {      m          i        ≥  1  ,  i  =  1  ,  2  ,  …  ,  k  } lacks a Hamiltonian cycle.}
}