On Spanning Wide Diameter of Graphs  

图的生成宽直径

作　　者：WANG Yameng YIMINGJIANG Shabier 汪亚蒙;依明江·沙比尔(新疆大学数学与系统科学学院,新疆乌鲁木齐830017)

机构地区：[1]School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China

出　　处：《新疆大学学报（自然科学版中英文）》2024年第5期571-578,590,共9页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：supported by the National Natural Science Foundation of the People's Republic of China“On disjoint path covers of graphs and related problems”(12261085);Natural Science Foundation of Xinjiang Uygur Autonomous Region of China“On spanning wide diameter and spanning cycle ability of interconnection networks”(2021D01C116)。

摘　　要：A t-container Ct(u,v)is a set of t internally disjoint paths between two distinct vertices u and v in a graph G,i.e.,Ct(u,v)={P_(1),P_(2),···,Pt}.Moreover,if V(P_(1))∪V(P_(2))∪···∪V(Pt)=V(G)then Ct(u,v)is called a spanning t-container,denoted by C_(t)^(sc)(u,v).The length of C_(t)^(sc)(u,v)={P_(1),P_(2),···,Pt}is l(C_(t)^(sc)(u,v))=max{l(P_(i))|1≤i≤t}.A graph G is spanning t-connected if there exists a spanning t-container between any two distinct vertices u and v in G.Assume that u and v are two distinct vertices in a spanning t-connected graph G.Let D_(t)^(sc)(u,v)be the collection of all C_(t)^(sc)(u,v)’s.Define the spanning t-wide distance between u and v in G,d_(t)^(sc)(u,v)=min{l(C_(t)^(sc)(u,v))|C_(t)^(sc)(u,v)∈D_(t)^(sc)(u,v)},and the spanning t-wide diameter of G,D_(t)^(sc)(G)=max{d_(t)^(sc)(u,v)|u,v∈V(G)}.In particular,the spanning wide diameter of G is D_(κ)^(sc)(G),whereκis the connectivity of G.In the paper we provide the upper and lower bounds of the spanning wide diameter of a graph,and show that the bounds are best possible.We also determine the exact values of wide diameters of some well known graphs including Harary graphs and generalized Petersen graphs et al..图G中两个顶点u和v之间的一个t-container C_t(u,v)是u和v之间的t-条内部不交路的集合,即C_t(u,v)={P_(1),P_(2),···,P_t}.进一步,如果V(P_(1))∪V(P_(2))∪···∪V(P_t)=V(G),那么C_t(u,v)称为生成t-container,记作C_(t)^(sc)(u,v).用l(C_(t)^(sc)(u,v))=max{l(P_(i))|1≤i≤t}表示C_(t)^(sc)(u,v)={P_(1),P_(2),···,P_t}的长度.图G是生成t-连通的,如果任意两个顶点u和v之间存在一个生成t-container.设u和v是生成t-连通图G中的两个不同的顶点,D_(t)^(sc)(u,v)是图G中所有C_(t)^(sc)(u,v)的集合,则u和v之间的生成t-宽距离定义为d_(t)^(sc)(u,v)=min{l(C_(t)^(sc)(u,v))|C_(t)^(sc)(u,v)∈D_(t)^(sc)(u,v)},图G的生成t-宽直径定义为D_(t)^(sc)(G)=max{d_(t)^(sc)(u,v)|u,v∈V(G)}.特别的,图G的生成宽直径是D_(κ)^(sc)(G)(G),其中κ是图G的连通度.得到了一般图的生成宽直径的上下界,并证明了界是最优的.除此之外,确定了Harary图、广义Petersen图等常见图类的生成宽直径的精确值.

关 键 词：CONNECTIVITY spanning connectivity spanning laceability wide diameter spanning wide diameter 

分 类 号：O157.5[理学—数学]