It is proved that the strong product of two non-trivial complete graphs is a complete graph and has strong orientation. And then the exact values of the minimum strong radius and the minimum strong diameter of the strong product of the complete graph are determined, and the ranges of the maximum strong diameter and the maximum strong radius are also given. Besides, the above conclusion is extended to strong products of multiple complete graphs.
LIU Shuyang
,
LI Feng
,
YIN Haoran
. Strong radius and strong diameter of strong product of complete graphs[J]. Journal of Hebei University(Natural Science Edition), 2023
, 43(2)
: 121
-126
.
DOI: 10.3969/j.issn.1000-1565.2023.02.002
[1] SABIDUSSI G. Graph multiplication[J]. Math Z, 1959, 72(1): 446-457. DOI: 10.1007/BF01162967.
[2] YANG H, ZHANG X J. The independent domination numbers of strong product of two cycles[J]. J Discrete Math Sci Cryptogr, 2018, 21(7/8): 1495-1507. DOI: 10.1080/09720529.2017.1316988.
[3] PETERIN I, PLETER P I. Wiener index of strong product of graphs[J]. OpMath, 2018, 38(1): 81. DOI: 10.7494/opmath.2018.38.1.81.
[4] CASABLANCA R M, DANKELMANN P. Distance and Eccentric sequences to bound the Wiener index, Hosoya polynomial and the average eccentricity in the strong products of graphs[J]. Discrete Appl Math, 2019, 263: 105-117. DOI: 10.1016/j.dam.2018.07.009.
[5] 李峰,梁栋,徐宗本.字典乘积图的Euler性[J].工程数学学报, 2014, 31(3): 317-323. DOI: 10.3969/j.issn.1005-3085.2014.03.001.
[6] LIANG D, LI F, XU Z B. The number of spanning trees in a new lexicographic product of graphs[J]. Sci China Inf Sci, 2014, 57(11): 1-9. DOI: 10.1007/s11432-014-5110-z.
[7] LADINEK I H, SˇPACAPAN S. The diameter of strong orientations of strong products of graphs[J]. Quaest Math, 2020: 1-14. DOI: 10.2989/16073606.2020.1754958.
[8] 郝国亮, 谢智红.一类强定向的最小平均距离[J].河北大学学报(自然科学版), 2017, 37(2): 113-116. DOI: 10.3969/j.issn.1000-1565.2017.02.001.
[9] SˇPACAPAN S. The diameter of strong orientations of Cartesian products of graphs[J]. Discrete Appl Math, 2018, 247: 116-121. DOI: 10.1016/j.dam.2018.03.062.
[10] DONALD J, ELWIN J. On the structure of the strong orientations of a graph[J]. SIAM J Discrete Math, 1993, 6(1): 30-43. DOI: 10.1137/0406003.
[11] AKSOY S, HORN P. Graphs with many strong orientations[J]. SIAM J Discrete Math, 2016, 30(2): 1269-1282. DOI: 10.1137/15M1018885.
[12] BAU S, DANKELMANN P. Diameter of orientations of graphs with given minimum degree[J]. Eur J Combin, 2015, 49: 126-133. DOI: 10.1016/j.ejc.2015.03.003.
[13] CHARTRAND G, ERWIN D, RAINES M, et al. Strong distance in strong digraphs[J]. Journal of Combinatorial Mathematics and Combinatorial Computing, 1999, 31: 33-44.
[14] 黄怡,陈美润.路和路的笛卡尔积的最小和最大定向强半径和强直径[J].新疆大学学报(自然科学版), 2009, 26(1): 33-37. DOI: 10.3969/j.issn.1000-2839.2009.01.005.
[15] 张果香.若干特殊图的最小强直径定向[D].太原: 山西大学, 2009.
[16] CHEN M R, GUO X F, ZHAI S H. The optimal strong radius and optimal strong diameter of the Cartesian product graphs[J]. Appl Math Lett, 2011, 24(5): 657-660. DOI: 10.1016/j.aml.2010.12.001.
[17] CHEN M R, GUO X F. Lower and upper orientable strong radius and strong diameter of the cartesian product of complete graphs [J]. Ars Combinatoria, 2010, 97(97): 175-182. DOI: 10.1007/s11512-009-0113-5.
[18] 杨超,徐俊明.强乘积图的连通度和边连通度(英文)[J].中国科学技术大学学报, 2008, 38(5):449-455.
[19] ROBBINS H E. A theorem on graphs, with an application to a problem of traffic control[J]. Am Math Mon, 1939, 46(5): 281. DOI: 10.2307/2303897.
[20] CHARTRAND G, ERWIN D, RAINES M, et al. On strong distance in strong oriented graphs[J]. Congr Numer, 1999, 138: 49-63. DOI: 10.1016/S0012-365X(02)00807-5.
[21] JUAN J S, HUANG C M. The strong distance problems[C] //Parallel and Distributed Processing Techniques and Applications, 2004: 699-708.
[22] DANKELMANN P, SWART H C, DAY D P. On strong distances in oriented graphs[J]. Discrete Math, 2003, 266(1/2/3): 195-201. DOI: 10.1016/s0012-365x(02)00807-5.
[23] JUAN J S T, HUANG C M, SUN I F. The strong distance problem on the Cartesian product of graphs[J]. Inf Process Lett, 2008, 107(2): 45-51. DOI: 10.1016/j.ipl.2008.01.001. (
