带弦圈的最小2宽直径(英文)

On the Minimum 2-wide Diameter of Cycles with Chords

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

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 l 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 that h（n, 2） = [n/2]. Furthermore, we give the bounds for h（n, t） when t ≥ 3.