Sufficient conditions for bipartite graphs to be super-k-restricted edge connected
Sufficient conditions for bipartite graphs to be super-k-restricted edge connected
复制标题
DOI：
10.1016/j.disc.2008.07.022
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Jun Yuan;Aixia Liu;Shiying Wang
中科院分区：
文献类型：
--
作者：
Jun Yuan;Aixia Liu;Shiying Wang
对于连通图G=(V，E)，如果G−S不连通且G−S的每个分量至少包含k个顶点，则边集S∧E是k限制边割。G的k限制边连通性用λk(G)表示，定义为最小k限制边切割的基数。对于U1，U2∧V(G)，用[U1，U2]表示一端在U1，另一端在U2的G的边的集合。定义ξk (G) =分钟{| (U, V (G)∖U) |: U⊂V (G) | | = k≥1 U和子图由U连接}。如果λk(G)=ξk(G)，则图G是λk最优的。进一步地，如果每一个最小k限制边切割都是某k阶连通子图的边的集合，则G为超k限制边连通或为简单起见称其为超λk。设k为正整数，设G为n≥4阶的二部图，二分（X，Y）。在本文中，我们证明了：(a)如果G有一个匹配，使得对于任意u，v∈X和任意u，v∈Y, |N(u)∩N(v)|≥2，则G是λ2最优的；(b)如果G有一个匹配，对于任意u，v∈X和任意u，v∈Y，使X中的每个顶点或Y中的每个顶点饱和且|N(u)∩N(v)|≥3，则G是超-λ2；(c)最小度δ(G)≥n+2k4，则G为λk最优；(d)最小度δ(G)≥n+2k+34，则G为超λk。
For a connected graph G=(V,E), an edge set S⊂E is a k-restricted edge cut if G−S is disconnected and every component of G−S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λk(G), is defined as the cardinality of a minimum k-restricted edge cut. For U1,U2⊂V(G), denote the set of edges of G with one end in U1and the other in U2by [U1,U2]. Define ξk(G)=min{|[U,V(G)∖U]|:U⊂V(G),|U|=k≥1 and the subgraph induced by U is connected}. A graph G is λk-optimal if λk(G)=ξk(G). Furthermore, if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k, then G is said to be super-k-restricted edge connected or super-λkfor simplicity. Let k be a positive integer and let G be a bipartite graph of order n≥4 with the bipartition (X,Y). In this paper, we prove that: (a) If G has a matching that saturates every vertex in X or every vertex in Y and |N(u)∩N(v)|≥2 for any u,v∈X and any u,v∈Y, then G is λ2-optimal; (b) If G has a matching that saturates every vertex in X or every vertex in Y and |N(u)∩N(v)|≥3 for any u,v∈X and any u,v∈Y, then G is super-λ2; (c) If the minimum degree δ(G)≥n+2k4, then G is λk-optimal; (d) If the minimum degree δ(G)≥n+2k+34, then G is super-λk.