不含三角形的图的λ_3-最优性的充分条件(英文)  

Sufficient Conditions for λ_3-Optimality of Triangle-Free Graphs

作　　者：郭利涛[1,2] 孟吉翔[2] 

机构地区：[1]厦门大学数学科学学院,厦门361005 [2]新疆大学数学与系统科学学院,乌鲁木齐830046

出　　处：《运筹学学报》2008年第4期25-31,共7页Operations Research Transactions

基　　金：supported by NSFC (No.10671165);XJEDU (No.2004G05).

摘　　要：设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件.Let G = （V,E） be a connected graph. An edge set S C E is a 3-restricted- edge-cut, if G- S is disconnected and every component of G - S has at least three vertices. The 3-restricted-edge-connectivity λ3 （G） of G is the cardinality of a minimum 3-restricted- edge-cut of G. A graph G is λ3-connected, if 3-restricted-edge-cuts exist. A graph G is called λ3-optimal, if λ3（G） = §3（G）, where §3（G） = min{/[U,U]/： U∈V, /U/ = 3 and G[U] is connected}. G[U] is the subgraph of G induced by the vertex subset U∈V, and U^-= V／U is the complement of U.[U,U^-] is the set of edges with one end in U and the other in U^-. In this paper, we give some sufficient conditions for triangle-free graphs to be λ3-optimal.

关 键 词：运筹学 限制性边连通度 3-限制性边连通度 不含三角形 

分 类 号：O123.1[理学—数学] O224[理学—基础数学]