Supereulerian graphs in the graph family C2(6,k) C 2 ( 6 , k )
For integers l l and k k with l>0 l > 0 , and k?0 k ? 0 , Ch(l,k) C h ( l , k ) denotes the collection of h h -edge-connected simple graphs G G on n n vertices such that for every edge-cut X X with 2?|X|?3 2 ? | X | ? 3 , each component of G?X G ? X has at least (n?k)/l ( n ? k ) / l vertices. We prove that for any integer k>0 k > 0 , there exists an integer N=N(k) N = N ( k ) such that for any n?N n ? N , any graph G?C2(6,k) G ? C 2 ( 6 , k ) on n n vertices is supereulerian if and only if G G cannot be contracted to a member in a well-characterized family of graphs. This extends former results in [J. Adv. Math. 28 (1999) 6569] by Catlin and Li, in [Discrete Appl. Math. 120 (2002) 3543] by Broersma and Xiong, in [Discrete Appl. Math. 145 (2005) 422428] by D. Li, Lai and Zhan, and in [Discrete Math. 309 (2009) 29372942] by X. Li, D. Li and Lai.
supereulerian graphs contraction collapsible graphs reduction