کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647840 1342380 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Balanced generic circuits without long paths
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Balanced generic circuits without long paths
چکیده انگلیسی

We call a graph G=(V,E)G=(V,E) a (k,ℓ)(k,ℓ)-circuit   if |E|=k|V|−ℓ+1|E|=k|V|−ℓ+1 and every X⊂VX⊂V with 2≤|X|≤|V|−12≤|X|≤|V|−1 induces at most k|X|−ℓk|X|−ℓ edges. A (2,3)(2,3)-circuit is also called a generic circuit. We say that a graph is balanced if the difference between its maximum and minimum degrees is at most 1. Graver et al. asked in Graver et al. (1993)  [7] whether a balanced generic circuit always admits a decomposition into two disjoint Hamiltonian paths. We show that this does not hold, moreover there are balanced (k,k+1)(k,k+1)-circuits for all k≥2k≥2 which do not contain any Hamiltonian path nor a path longer than |V|λ|V|λ for λ>log8log9≃0,9464.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 15, 6 August 2012, Pages 2262–2271
نویسندگان
, ,