Article

Spanning trails containing given edges

Discrete Mathematics
Document Type

Article
Publication Date

1-1-2006
Disciplines

DOI

http://dx.doi.org/10.1016/j.disc.2005.10.022
Abstract

A graph GG is Eulerian-connected if for any uu and vv in V(G)V(G), GG has a spanning (u,v)(u,v)-trail. A graph GG is edge-Eulerian-connected if for any e′e′ and e″e″ in E(G)E(G), GG has a spanning (e′,e″)(e′,e″)-trail. For an integer r⩾0r⩾0, a graph is called rr-Eulerian-connected if for any X⊆E(G)X⊆E(G) with |X|⩽r|X|⩽r, and for any View the MathML sourceu,v∈V(G), GG has a spanning (u,v)(u,v)-trail TT such that X⊆E(T)X⊆E(T). The rr-edge-Eulerian-connectivity of a graph can be defined similarly. Let θ(r)θ(r) be the minimum value of kk such that every kk-edge-connected graph is rr-Eulerian-connected. Catlin proved that θ(0)=4θ(0)=4. We shall show that θ(r)=4θ(r)=4 for 0⩽r⩽20⩽r⩽2, and θ(r)=r+1θ(r)=r+1 for r⩾3r⩾3. Results on rr-edge-Eulerian connectivity are also discussed.
Rights

This is a pre-print version of this article. The version of record is available at Elsevier.

Citation Information

Zhi-Hong Chen, Weiqi Luo and Wei-Guo Chen. "Spanning trails containing given edges" *Discrete Mathematics*Vol. 306 Iss. 1 (2006) p. 87 - 98

Available at: http://works.bepress.com/zhi_hong_chen/5/