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

Ce Zhang; Feng Li; Ce Zhang; Feng Li

doi:10.3934/math.2026382

AIMS Mathematics

2026, Volume 11, Issue 4: 9260-9283. doi: 10.3934/math.2026382

Previous Article Next Article

Research article Special Issues

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

Ce Zhang ,
Feng Li ^,

College of Computer Science, Qinghai Normal University, Xining, 810008, China

Received: 13 January 2026 Revised: 06 March 2026 Accepted: 19 March 2026 Published: 03 April 2026
MSC : 05C12, 05C69, 05C76

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, \ldots, m_k}\otimes P_n $ by taking the complete multipartite graph $ K_{m_1, m_2, \ldots, m_k} |\{m_{i}\geq1, 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, \ldots, m_k} \otimes P_n $, establishing its exact value and bounds for the cases in which $ K_{m_1, m_2, \ldots, m_k} |\{m_{i}\geq1, 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, \ldots, m_k} \otimes P_n $. Through simulation experiments, we find that the high-dimensional strong product network $ K_{m_1, m_2, \ldots, m_k} \otimes P_n $ demonstrates superior information transfer efficiency when the underlying graph $ K_{m_1, m_2, \ldots, m_k} |\{m_{i}\geq1, i = 1, 2, \dots, k\} $ lacks a Hamiltonian cycle.
- strong product graph,
- maximum strong diameter,
- complete multipartite graph,
- path
Citation: Ce Zhang, Feng Li. Maximum strong diameter of the strong product of complete multipartite graph and path[J]. AIMS Mathematics, 2026, 11(4): 9260-9283. doi: 10.3934/math.2026382

Related Papers:

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, \ldots, m_k}\otimes P_n $ by taking the complete multipartite graph $ K_{m_1, m_2, \ldots, m_k} |\{m_{i}\geq1, 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, \ldots, m_k} \otimes P_n $, establishing its exact value and bounds for the cases in which $ K_{m_1, m_2, \ldots, m_k} |\{m_{i}\geq1, 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, \ldots, m_k} \otimes P_n $. Through simulation experiments, we find that the high-dimensional strong product network $ K_{m_1, m_2, \ldots, m_k} \otimes P_n $ demonstrates superior information transfer efficiency when the underlying graph $ K_{m_1, m_2, \ldots, m_k} |\{m_{i}\geq1, i = 1, 2, \dots, k\} $ lacks a Hamiltonian cycle.

References

[1]	G. Chartrand, D. Erwin, M. Raines, P. Zhang, Strong distance in strong digraphs, J. Combin. Math. Combin. Comput., 31 (1999), 33–44.
[2]	K. Balakrishnan, M. Changat, I. Peterin, S. Špacapan, P. Šparl, A. R. Subhamathi, Strongly distance-balanced graphs and graph products, Eur. J. Comb., 30 (2009), 1048–1053. https://doi.org/10.1016/j.ejc.2008.09.018 doi: 10.1016/j.ejc.2008.09.018
[3]	F. Li, W. Wang, Z. B. Xu, H. X. Zhao, Some results on the lexicograpsic product of vertex-transitive graphs, Appl. Math. Lett., 24 (2011), 1924–1926. https://doi.org/10.1016/j.aml.2011.05.021 doi: 10.1016/j.aml.2011.05.021
[4]	W. M. Qian, F. Li, Exact vertex forwarding index of the strong product of complete graph and cycle, Discrete Appl. Math., 361 (2025), 69–84. https://doi.org/10.1016/j.dam.2024.09.016 doi: 10.1016/j.dam.2024.09.016
[5]	Y. X. Yue, F. Li, Fault diameter of strong product graph of two paths, In: Artificial intelligence for communications and networks, Cham: Springer, 2023, 20–33. https://doi.org/10.1007/978-3-031-29126-5_2
[6]	R. J. Li, S. F. Chen, The oriented diameter of a bridgeless graph with the given path $P_k$, Discrete Math., 348 (2025), 114509. https://doi.org/10.1016/j.disc.2025.114509 doi: 10.1016/j.disc.2025.114509
[7]	M. Surmacs, Improved bound on the oriented diameter of graphs with given minimum degree, Eur. J. Comb., 59 (2017), 187–191. https://doi.org/10.1016/j.ejc.2016.08.006 doi: 10.1016/j.ejc.2016.08.006
[8]	Y. W. Ge, X. N. Liu, Z. Y. Wang, On the oriented diameter of near planar triangulations, Discrete Math., 348 (2025), 114406. https://doi.org/10.1016/j.disc.2025.114406 doi: 10.1016/j.disc.2025.114406
[9]	B. Chen, A. Chang, Oriented diameter of graphs with given girth and maximum degree, Discrete Math., 346 (2023), 113287. https://doi.org/10.1016/j.disc.2022.113287 doi: 10.1016/j.disc.2022.113287
[10]	J. Bračič, B. Kuzma, On the diameter of a super-order-commuting graph, Discrete Math., 348 (2025), 114385. https://doi.org/10.1016/j.disc.2024.114385 doi: 10.1016/j.disc.2024.114385
[11]	L. Aragão, M. Collares, G. Dahia, J. P. Marciano, The diameter of randomly twisted hypercubes, Eur. J. Comb., 124 (2025), 104078. https://doi.org/10.1016/j.ejc.2024.104078 doi: 10.1016/j.ejc.2024.104078
[12]	A. V. Ledezma, A. Pastine, P. Torres, M. Valencia-Pabon, On the diameter of Schrijver graphs, Discrete Appl. Math., 350 (2024), 15–30. https://doi.org/10.1016/j.dam.2024.02.019 doi: 10.1016/j.dam.2024.02.019
[13]	S. K. Zhou, F. Li, Minimum and maximum strong diameters of the Cartesian and strong products of cycles, J. Combin. Math. Combin. Comput., 125 (2025), 165–184. https://doi.org/10.61091/jcmcc125-12 doi: 10.61091/jcmcc125-12
[14]	R. Haller, J. Langemets, V. Lima, R. Nadel, Symmetric strong diameter two property, Mediterr. J. Math., 16 (2019), 35. https://doi.org/10.1007/s00009-019-1306-1 doi: 10.1007/s00009-019-1306-1
[15]	G. López-Pérez, M. Martín, A. R. Zoca, Strong diameter two property and convex combinations of slices reaching the unit sphere, Mediterr. J. Math., 16 (2019), 122. https://doi.org/10.1007/s00009-019-1403-1 doi: 10.1007/s00009-019-1403-1
[16]	P. Dankelmann, Y. Guo, E. J. Rivett-Carnac, L. Volkmann, The oriented diameter of graphs derived from other graphs, Discrete Math., 348 (2025), 114443. https://doi.org/10.1016/j.disc.2025.114443 doi: 10.1016/j.disc.2025.114443
[17]	S. Špacapan, The diameter of strong orientations of Cartesian products of graphs, Discrete Appl. Math., 247 (2018), 116–121. https://doi.org/10.1016/j.dam.2018.03.062 doi: 10.1016/j.dam.2018.03.062
[18]	S. Aksoy, P. Horn, Graphs with many strong orientations, SIAM J. Discrete Math., 30 (2016), 1269–1282. https://doi.org/10.1137/15M1018885 doi: 10.1137/15M1018885
[19]	F. Botler, C. Hoppen, G. O. Mota, Counting orientations of graphs with no strongly connected tournaments, Discrete Math., 345 (2022), 113024. https://doi.org/10.1016/j.disc.2022.113024 doi: 10.1016/j.disc.2022.113024
[20]	C. Thomassen, Strongly 2-connected orientations of graphs, J. Comb. Theory Ser. B, 110 (2015), 67–78. https://doi.org/10.1016/j.jctb.2014.07.004 doi: 10.1016/j.jctb.2014.07.004
[21]	S. Bau, P. Dankelmann, Diameter of orientations of graphs with given minimum degree, Eur. J. Comb., 49 (2015), 126–133. https://doi.org/10.1016/j.ejc.2015.03.003 doi: 10.1016/j.ejc.2015.03.003
[22]	K. S. A. Kumar, B. Sasidharan, K. S. Sudeep, On oriented diameter of $(n, k)$-star graphs, Discrete Appl. Math., 354 (2024), 214–228. https://doi.org/10.1016/j.dam.2022.04.017 doi: 10.1016/j.dam.2022.04.017
[23]	P. Dankelmann, H. C. Swart, D. P. Day, On strong distance in oriented graphs, Discrete Math., 266 (2003), 195–201. https://doi.org/10.1016/S0012-365X(02)00807-5 doi: 10.1016/S0012-365X(02)00807-5
[24]	F. Boesch, R. Tindell, Robbins's theorem for mixed multigraphs, Amer. Math. Monthly, 87 (1980), 716–719. https://doi.org/10.2307/2321858 doi: 10.2307/2321858
[25]	M. M. M. Jaradat, On the edge coloring of graph products, Int. J. Math. Math. Sci., 2005 (2005), 2669–2676. https://doi.org/10.1155/IJMMS.2005.2669 doi: 10.1155/IJMMS.2005.2669
[26]	H. F. Miao, X. F. Guo, Lower and upper orientable strong radius and strong diameter of complete $k$-partite graphs, Discrete Appl. Math., 154 (2006), 1606–1614. https://doi.org/10.1016/j.dam.2006.01.010 doi: 10.1016/j.dam.2006.01.010
[27]	R. H. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, Boca Raton: CRC Press, 2011.

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)