图的生成宽直径（英文）

摘要

图G中两个顶点u和v之间的一个t-container C_t（u,v）是u和v之间的t-条内部不交路的集合,即C_t（u,v）={P₁,P₂,···,P_t}.进一步,如果V（P₁）∪V（P₂）∪···∪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₁,P₂,···,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的连通度.得到了一般图的生成宽直径的上下界,并证明了界是最优的.除此之外,确定了Harary图、广义Petersen图等常见图类的生成宽直径的精确值.

关键词

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