图的生成宽直径(英文)

汪亚蒙, 依明江·沙比尔

新疆大学学报(自然科学版中英文) ›› 2024, Vol. 41 ›› Issue (05) : 571-578+590. DOI: 10.13568/j.cnki.651094.651316.2023.11.21.0001

图的生成宽直径(英文)

  • 汪亚蒙, 依明江·沙比尔
作者信息 +
History +

摘要

图G中两个顶点u和v之间的一个t-container C_t(u,v)是u和v之间的t-条内部不交路的集合,即C_t(u,v)={P1,P2,···,P_t}.进一步,如果V(P1)∪V(P2)∪···∪V(P_t)=V(G),那么C_t(u,v)称为生成t-container,记作C _tsc(u,v).用l(C_tsc(u,v))=max{l(Pi)|1≤i≤t}表示C _tsc(u,v)={P1,P2,···,P_t}的长度.图G是生成t-连通的,如果任意两个顶点u和v之间存在一个生成t-container.设u和v是生成t-连通图G中的两个不同的顶点,D_tsc(u,v)是图G中所有C _tsc(u,v)的集合,则u和v之间的生成t-宽距离定义为d_tsc(u,v)=min{l(C_tsc(u,v))|C_tsc(u,v)∈D_tsc(u,v)},图G的生成t-宽直径定义为D_tsc(G)=max{d_tsc(u,v)|u,v∈V(G)}.特别的,图G的生成宽直径是Dκsc(G),其中κ是图G的连通度.得到了一般图的生成宽直径的上下界,并证明了界是最优的.除此之外,确定了Harary图、广义Petersen图等常见图类的生成宽直径的精确值.

关键词

连通性 / 生成连通性 / 生成可系性 / 宽直径 / 生成宽直径

中图分类号

O157.5

引用本文

导出引用
汪亚蒙, 依明江·沙比尔. 图的生成宽直径(英文). 新疆大学学报(自然科学版中英文). 2024, 41(05): 571-578+590 https://doi.org/10.13568/j.cnki.651094.651316.2023.11.21.0001

基金

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)

评论

Accesses

Citation

Detail

段落导航
相关文章

/