带弦圈的最小2宽直径

设k为正整数,G是简单k连通图.图G的k宽直径,dk(G),是指最小的整数ι使得对任意两不同顶点x,y∈V(G),都存在k条长至多为ι的内部不交的连接x和y的路.用C(n,t)表示在圈Gn上增加t条边所得的图.定义h(n,t):min{d2(C(n,t))}.本文给出了h(n,2)=[n/2].而且,给出了当t较大时h(n,t)的界.

On the Minimum 2-wide Diameter of Cycles with Chords

Let k be a positive integer and G be a k-connected simple graph. The k-wide diameter of graph G, dk(G), is the minimum integer ι such that for any two distinct vertices x, y ∈ V(G), there are k (internally) disjoint paths with lengths at most l between x and y. Let C(n, t) be the resulting graph by adding t edges to cycle Cn. Define h(n,t) =- min{d2(C(n,t))}. In this paper, we compute h(n,t) and obtain thai h(n, 2) = [n/2] Furthermore, we give the bounds for h(n,t) when t ≥3.