Article
Spanning trails in essentially 4-edge-connected graphs
Discrete Applied Mathematics
(2014)
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
- collapsible,
- essentially 4-edge-connected,
- r-edge-Eulerian-connected,
- spanning trail
Disciplines
Publication Date
January, 2014
DOI
https://doi.org/10.1016/j.dam.2013.08.041
Publisher Statement
Note: full-text not available due to publisher restrictions. Link takes you to an external site where you can purchase the article or borrow it from a local library.
Citation Information
Jinquan Xu, Zhi-Hong Chen, Hong-Jian Lai and Meng Zhang. "Spanning trails in essentially 4-edge-connected graphs" Discrete Applied Mathematics Vol. 162 Iss. 10 (2014) p. 306 - 313 ISSN: 0166-218X Available at: http://works.bepress.com/zhi_hong_chen/24/