有向线图的等周弧连通度(英文)

Isoperimetric Arc Connectivity of Line Digraphs

一个有向图D的k-阶等周弧连通度定义为:γ+k(D)=min{|(U,U)|:U?V,|U|≥k,|U|≥k}.一个有向图满足γ+k(D)=β+k(D)时称为是γ+k-最优的,其中β+k(D)=min{|(U,U)|:U?V,|U|=k,|U|≥k}.假设D是强连通d-正则的有向图且κ(D)≥3.本文我们证明了L(D)是γ+2-最优的,其中L(D)表示D的线图.

The k-isoperimetric-arc-connectivity of a digraph D is defined asγ^k＋ （D）=min{｜（U,U^-）｜：U→∪V,｜U｜≥k,｜U^-｜≥k}. A digraph withγ^k＋ （D）=β＋k （D） is calledγ＋k-optimal, whereβ^k＋ （D）=min{｜（U,U）｜：U→∪V, ｜U｜=k, ｜U^-｜≥k}. Suppose D is a strongly connected d-regular digraph withκ（D）≥3. In this paper, we prove that L（D） isγ＋2-optimal, where L（D） is the line graph of D.