Spanning trails in essentially 4-edge-connected graphs
Spanning trails in essentially 4-edge-connected graphs
复制标题
DOI：
10.1016/j.dam.2013.08.041
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Jinquan Xu;Zhi-Hong Chen;H. Lai;Meng Zhang
中科院分区：
文献类型：
--
作者：
Jinquan Xu;Zhi-Hong Chen;H. Lai;Meng Zhang
连通图G是本质4-边连通的，如果对G的任意边割X，|X| < 4，则G-X是连通的，或者G-X的至多一个分支有边。在本文中，我们引入了一种约化方法，并研究了本质4-边连通图的生成迹的存在性。作为应用，我们证明了：如果G是4-边连通的，则对任意边子集X 0 ∈ E（G），|X 0的|≤ 3且任意不同的边e，e′∈ E（G），则G有一个包含X 0中所有边的生成（e，e′）-迹，从而解决了[W.罗，Z- H.陈文G. Chen，Spanning trails containing given edges，Discrete Math.306（2006）87-98]。
A connected graph G is essentially 4-edge-connected if for any edge cut X of G with| X|< 4, either G− X is connected or at most one component of G− X has edges. In this paper, we introduce a reduction method and investigate the existence of spanning trails in essentially 4-edge-connected graphs. As an application, we prove that if G is 4-edge-connected, then for any edge subset X 0⊆ E (G) with| X 0|≤ 3 and any distinct edges e, e′∈ E (G), G has a spanning (e, e′)-trail containing all edges in X 0, which solves a conjecture posed in [W. Luo, Z.-H. Chen, W.-G. Chen, Spanning trails containing given edges, Discrete Math. 306 (2006) 87–98].