Publications
Sort:
Open Access Research Article Issue
Maximum strong diameter of the strong product of complete multipartite graph and path
AIMS Mathematics 2026, 11(4): 9260-9283
Published: 03 April 2026
Abstract PDF (14 MB) Collect
Downloads:8

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.

Total 1