完全图强乘积的强半径和强直径

doi:10.3969/j.issn.1000-1565.2023.02.002

河北大学学报(自然科学版) ›› 2023, Vol. 43 ›› Issue (2): 121-126.DOI: 10.3969/j.issn.1000-1565.2023.02.002

完全图强乘积的强半径和强直径

刘树洋^1,2,李峰^1,2,阴浩然¹

收稿日期:2022-04-25 出版日期:2023-03-25 发布日期:2023-04-06
通讯作者: 李峰(1981—)
作者简介:刘树洋(1997—),男,江西抚州人,青海师范大学在读硕士研究生,主要从事组合网络理论及优化方向研究.
E-mail:liushuyang2021@163.com
基金资助:
国家自然科学基金资助项目(11551002);青海省自然科学基金资助项目(2019-ZJ-7093)

Strong radius and strong diameter of strong product of complete graphs

LIU Shuyang^1,2,LI Feng^1,2,YIN Haoran¹

1. College of Computer Science, Qinghai Normal University, Xining 810008, China; 2. The State Key Laboratory of Tibetan Intelligent Information Processing and Application, Xining 810008, China

Received:2022-04-25 Online:2023-03-25 Published:2023-04-06

摘要/Abstract

摘要： 首先证明2个非平凡完全图强乘积是完全图且具有强定向性,然后确定了完全图强乘积的最小强半径和最小强直径的精确值,给出了最大强直径和最大强半径的范围.最后通过利用强乘积的结合性,将上述结论推广到多个完全图的强乘积.

关键词: 完全图, 强乘积, 强定向, 强半径, 强直径

Abstract: 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.

Key words: complete graph, strong product, strong orientation, strong radius, strong diameter

中图分类号:

O157.5

刘树洋,李峰,阴浩然. 完全图强乘积的强半径和强直径[J]. 河北大学学报(自然科学版), 2023, 43(2): 121-126.

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.

参考文献

[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. (

完全图强乘积的强半径和强直径

Strong radius and strong diameter of strong product of complete graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价