Degree conditions for graphs to be maximally k-restricted edge connected and super k-restricted edge connected
Degree conditions for graphs to be maximally k-restricted edge connected and super k-restricted edge connected
复制标题
图最大 k 限制边连通和超 k 限制边连通的度条件
DOI：
10.1016/j.dam.2014.10.027
复制
发表时间：
2015-03
影响因子：
1.1
通讯作者：
Zhao Nana
中科院分区：
文献类型：
--
作者：
Wang Shiying;Zhao Nana
对于连通图 G=(V, E)，如果 G− S 是断开的并且 G− S 的每个分量至少有 k 个顶点，则边集 S⊆ E (G) 称为 G 的 k 限制边割。 G 的 k 限制边连通性，用 λ k (G) 表示，定义为最小 k 限制边切割的基数。对于 G 的两个不相交的顶点子集 X, Y，定义 [X, Y]={x y ∈ E (G): x ∈ X, y ∈ Y} 并定义 xi k (G)= min {|[X, X ́]|: X⊆ V (G),| X|= k，G [X] 是连通的}，其中 X¯= V (G)∖ X。如果 λ k (G)= xi k (G)，则 G 是 λ k 最优。此外，如果 G 的每个最小 k 限制边割都隔离一个阶数为 k 的连通子图，则 G 是超 λ k。 k-限制边连通性是评估网络可靠性的重要指标。本文给出了图最大k限制边连通和超k限制边连通的一定程度的条件。
For a connected graph G=(V, E), an edge set S⊆ E (G) is called a k-restricted edge cut of G if G− S is disconnected and every component of G− S has 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 two disjoint vertex subsets X, Y of G, define [X, Y]={x y∈ E (G): x∈ X, y∈ Y} and define ξ k (G)= min {|[X, X¯]|: X⊆ V (G),| X|= k, G [X] is connected}, where X¯= V (G)∖ X. G is λ k-optimal if λ k (G)= ξ k (G). Furthermore, G is super-λ k if every minimum k-restricted edge cut of G isolates a connected subgraph with order k. The k-restricted edge connectivity is an important index to estimate the reliability of networks. In this paper, some degree conditions for graphs to be maximally k-restricted edge connected and super k-restricted edge connected are given.
登录
查看更多内容
影响因子：
0.5
作者：
Shiying Wang;Lei Zhang;Shangwei Lin
通讯作者：
Shangwei Lin
DOI：
10.1016/j.disc.2005.04.020
发表时间：
2005-11
期刊：
Discret. Math.
影响因子：
--
作者：
Zhao Zhang;Jinjiang Yuan
通讯作者：
Zhao Zhang;Jinjiang Yuan
DOI：
10.1016/s0012-365x(02)00299-6
发表时间：
2002-12
期刊：
Discret. Math.
影响因子：
--
作者：
Ming Wang;Qiao Li
通讯作者：
Ming Wang;Qiao Li
影响因子：
1.4
作者：
Wang Yingqian Li Qiao
通讯作者：
Wang Yingqian Li Qiao
影响因子：
2.1
作者：
Li Shang;Heping Zhang
通讯作者：
Li Shang;Heping Zhang