Super restricted edge connectivity of regular edge-transitive graphs
Super restricted edge connectivity of regular edge-transitive graphs
复制标题
规则边传递图的超限制边连通性
DOI：
10.1016/j.dam.2011.12.004
复制
发表时间：
2012-05
影响因子：
1.1
通讯作者：
Zhou, Jin-Xin
中科院分区：
文献类型：
--
作者：
Zhou, Jin-Xin
如果连通图的边切割将图分成至少为2阶的分量，则称为受限边切割；当G−F对G的每一个最小限制边切F都包含一条孤立边时，则图G是超限制边连通的。本文证明了至少3价的连通正则边传递图当且仅当它是三维超立方体，或周长至少为6阶的四价边传递图不是超限制边连通的。因此，存在无穷多个k≥3的非超限制边连通的k正则哈密顿图。这就否定了[J]中的问题。欧峰，张锋，正则图的超受限边连通性，图与组合，21(2005)459-467]，关于受限边连通图与哈密顿图的关系。
An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least 2; a graph G is super restricted edge connected if G−F contains an isolated edge for every minimum restricted edge cut F of G. It is proved in this paper that a connected regular edge-transitive graph of valency at least 3 is not super restricted edge connected if and only if it is either the three dimensional hypercube, or a tetravalent edge-transitive graph of girth 3 and of order at least 6. As a result, there are infinitely many k-regular Hamiltonian graphs with k≥3 which are not super restricted edge connected. This answers negatively a question in [J. Ou, F. Zhang, Super restricted edge connectivity of regular graphs, Graphs & Combin. 21 (2005) 459–467] regarding the relationship between restricted edge connected graphs and Hamiltonian graphs.
登录
查看更多内容
DOI：
10.2307/3616070
发表时间：
1973-12
期刊：
The Mathematical Gazette
影响因子：
--
作者：
K. Fraughnaugh
通讯作者：
K. Fraughnaugh
DOI：
10.1007/978-1-4419-8698-6
发表时间：
2003-07
期刊：
--
影响因子：
--
作者：
Junming Xu
通讯作者：
Junming Xu
DOI：
10.1007/978-1-4613-0163-9
发表时间：
2001-04
期刊：
--
影响因子：
--
作者：
C. D. Godsil;G. Royle
通讯作者：
C. D. Godsil;G. Royle
DOI：
10.1007/978-3-8348-9329-1_2
发表时间：
2010
期刊：
--
影响因子：
--
作者：
M. Loebl
通讯作者：
M. Loebl
影响因子：
6.9
作者：
Junming Xu
通讯作者：
Junming Xu