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

摘要

一个有向图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的线图.