2023年河北大学学报(自然科学版)2023第43卷第2期JournalofHebeiUniversity(NaturalScienceEdition)Vol.43No.2DOI:10.3969/j.issn.10001565.2023.02.002完全图强乘积的强半径和强直径刘树洋1,2,李峰1,2,阴浩然1(1.青海师范大学计算机学院,青海西宁810008;2.藏语智能信息处理及应用国家重点实验室,青海西宁810008)摘要:首先证明2个非平凡完全图强乘积是完全图且具有强定向性,然后确定了完全图强乘积的最小强半径和最小强直径的精确值,给出了最大强直径和最大强半径的范围.最后通过利用强乘积的结合性,将上述结论推广到多个完全图的强乘积.关键词:完全图;强乘积;强定向;强半径;强直径中图分类号:O157.5文献标志码:A文章编号:10001565(2023)02012106StrongradiusandstrongdiameterofstrongproductofcompletegraphsLIUShuyang1,2,LIFeng1,2,YINHaoran1(1.CollegeofComputerScience,QinghaiNormalUniversity,Xining810008,China;2.TheStateKeyLaboratoryofTibetanIntelligentInformationProcessingandApplication,Xining810008,China)Abstract:Itisprovedthatthestrongproductoftwonon-trivialcompletegraphsisacompletegraphandhasstrongorientation.Andthentheexactvaluesoftheminimumstrongradiusandtheminimumstrongdiameterofthestrongproductofthecompletegrapharedetermined,andtherangesofthemaximumstrongdiameterandthemaximumstrongradiusarealsogiven.Besides,theaboveconclusionisextendedtostrongproductsofmultiplecompletegraphs.Keywords:completegraph;strongproduct;strongorientation;strongradius;strongdiameter强乘积作为4种标准乘积之一,在互连网络设计中有着广泛的运用.其概念是Sabidussi[1]于1959年首次提出.对于2个图G1和G2的强乘积用G1G2表示.顶点集V(G1G2)={(x,y)│x∈V(G1),y∈V(G2)},2个不同的顶点(x1,y1)和(x2,y2)(其中x1,x2∈V(G1),y1,y2∈V(G2))相邻当且仅当x1=x2且y1,y2∈E(G2)或者y1=y2且x1,x2∈E(G1)或者x1,x2∈E(G1)且y1,y2∈E(G2),并且将G1和G2称为强乘积图G1G2的因子图.现在关于强乘积性质的研究非常多,如独立控制数[2]、Wiener指数[3-4]等.其他3种标准乘积也是图论中重要的研究方向,相关研究结果可见文献[5-6].1预备知识1个图G是指1个有序二元组(V(G),E(G)),其中V(G)是非空的顶点集,E(G)是边集.本文考虑的收稿日期:20220425基金项目:国家自然科学基金资助项目(11551002);青海省自然科学基金资助项目(2019-ZJ-70...
