On the existence of super edge-connected graphs with prescribed degrees
On the existence of super edge-connected graphs with prescribed degrees
复制标题
关于规定度超边连通图的存在性
DOI：
10.1016/j.disc.2014.03.025
复制
发表时间：
2014-08
影响因子：
0.8
通讯作者：
Zhang Zhao
中科院分区：
文献类型：
--
作者：
Tian Yingzhi;Meng Jixiang;Lai Hongjian;Zhang Zhao
设G为n阶连通图，最小度δ (G)，边连通性κ ' (G)。当k′(G)= δ (G)时，图G是最大边连通的，当每个最小边切割由与最小度顶点相关的边组成时，图G是超边连通的。如果存在顶点为v1，…，vn的图，且当1≤i≤n时，d (vi)= d1，则图（d1，…，dn）是图。如果d是某个超边连通图的度数列表，则图列表d是超边连通图。证明了最小元素为1的图表D是超边连通的当且仅当(1)∑i= 1 n D i≥2n或(2)∑i= 1 n D i= 2 （n−1）且max {D i: 1≤i≤n}= n−1。给出了最小元素数为2的图表是超边连通的一个充分必要条件，并证明了每个最小元素数为3的图表都是超边连通的。
Let G be a connected graph of order n, minimum degree δ (G), and edge-connectivity κ′(G). The graph G is maximally edge-connected if κ′(G)= δ (G) and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. A list (d 1,…, d n) is graphic if there is a graph with vertices v 1,…, v n such that d (v i)= d i for 1≤ i≤ n. A graphic list D is super edge-connected if D is the degree list of some super edge-connected graph. We prove that a graphic list D with least element 1 is super edge-connected if and only if (1)∑ i= 1 n d i≥ 2 n or (2)∑ i= 1 n d i= 2 (n− 1) and max {d i: 1≤ i≤ n}= n− 1. We also give a necessary and sufficient condition for a graphic list with least entry 2 to be super edge-connected, and we show that every graphic list with least element at least 3 is super edge-connected.
登录
查看更多内容
影响因子：
1.4
作者：
W. Mader
通讯作者：
W. Mader
影响因子：
2.7
作者：
D. L. Wang
通讯作者：
D. L. Wang
DOI：
10.1137/0110037
发表时间：
1962-01-01
期刊：
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS
影响因子：
--
作者：
HAKIMI, SL
通讯作者：
HAKIMI, SL
DOI：
10.1016/s0195-6698(84)80034-7
发表时间：
1984-12
期刊：
Eur. J. Comb.
影响因子：
--
作者：
Y. O. Hamidoune
通讯作者：
Y. O. Hamidoune
影响因子：
2.1
作者：
Danielle Wang;D. Kleitman
通讯作者：
Danielle Wang;D. Kleitman