可迁图的超常边连通度的最优性  

OPTIMIZATION PROPERTIES OF EXTRA-EDGE-CONNECTIVITY FOR TRANSITIVE GRAPHS

作　　者：王铭[1] 李乔[1] 

机构地区：[1]上海交通大学数学系,上海200030

出　　处：《数学年刊（A辑）》2003年第3期315-320,共6页Chinese Annals of Mathematics

基　　金：国家自然科学基金(No.19971056);高校博士点专项基金(No.2000024837)

摘　　要：图的超常边连通度是图的边连通度概念的推广,对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λ_h一定存在(1≤h≤n/2)。本文证明了:当d_-正则的n_-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d_-正则的n_-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h:1≤h≤min{g-1,n/2},λ_h达到其最大可能值,即λ_h=hd-2(h-1)。The extra-edge-connectivity generalizes the concept of edge-connectivity of graphs. For a simple connected vertex-transitive or regular edge-transitive graph with order n, its kth extra-edge-connectivity λg always exist (1≤ h ≤n/2). In this paper, the authors prove: If a simple connected d-regular edge-transitive graph satisfies n ≥ 6, d ≥4 and girth g ≥5, or a simple connected d-regular edge-transitive graph satisfies n ≥ 6, d ≥ 4 and girth g ≥ 4, then λh can reach upper bound for any h :1 ≤ h≤min{g - 1, n/2}, i.e. λh=hd- 2(h - 1).

关 键 词：超常边连通度 最优性 点可迁图 正则边可迁图 

分 类 号：O157.5[理学—数学]