| کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن | 
|---|---|---|---|---|
| 9516212 | 1343771 | 2005 | 10 صفحه PDF | دانلود رایگان | 
عنوان انگلیسی مقاله ISI
												Girth and treewidth
												
											دانلود مقاله + سفارش ترجمه
													دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
																																												موضوعات مرتبط
												
													مهندسی و علوم پایه
													ریاضیات
													ریاضیات گسسته و ترکیبات
												
											پیش نمایش صفحه اول مقاله
												 
												چکیده انگلیسی
												The length of the shortest cycle in a graph G is called the girth of G. In particular, we show that if G has girth at least g and average degree at least d, then tw(G)=Ω(1g+1(dâ1)â(gâ1)/2â). In view of a famous conjecture regarding the existence of graphs with girth g, minimum degree δ and having at most c(δâ1)â(gâ1)/2â vertices (for some constant c), this lower bound seems to be almost tight (but for a multiplicative factor of g+1).
											ناشر
												Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 93, Issue 1, January 2005, Pages 23-32
											Journal: Journal of Combinatorial Theory, Series B - Volume 93, Issue 1, January 2005, Pages 23-32
نویسندگان
												L.Sunil Chandran, C.R. Subramanian,