Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872530 | Discrete Applied Mathematics | 2014 | 8 Pages |
Abstract
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 X0âE(G) with |X0|â¤3 and any distinct edges e,eâ²âE(G), G has a spanning (e,eâ²)-trail containing all edges in X0, 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].
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jinquan Xu, Zhi-Hong Chen, Hong-Jian Lai, Meng Zhang,