Article ID Journal Published Year Pages File Type
420200 Discrete Applied Mathematics 2011 11 Pages PDF
Abstract

For integers ll and kk with l>0l>0, and k≥0k≥0, Ch(l,k)Ch(l,k) denotes the collection of hh-edge-connected simple graphs GG on nn vertices such that for every edge-cut XX with 2≤|X|≤32≤|X|≤3, each component of G−XG−X has at least (n−k)/l(n−k)/l vertices. We prove that for any integer k>0k>0, there exists an integer N=N(k)N=N(k) such that for any n≥Nn≥N, any graph G∈C2(6,k)G∈C2(6,k) on nn vertices is supereulerian if and only if GG cannot be contracted to a member in a well-characterized family of graphs. This extends former results in [J. Adv. Math. 28 (1999) 65–69] by Catlin and Li, in [Discrete Appl. Math. 120 (2002) 35–43] by Broersma and Xiong, in [Discrete Appl. Math. 145 (2005) 422–428] by D. Li, Lai and Zhan, and in [Discrete Math. 309 (2009) 2937–2942] by X. Li, D. Li and Lai.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,