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

چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 312, Issue 15, 6 August 2012, Pages 2262–2271
نویسندگان
Csaba Király, Ferenc Péterfalvi,