کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872496 | 681651 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Lower bounds for treewidth of product graphs
ترجمه فارسی عنوان
محدوده های پایین برای عرض درخت نمودار محصول
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درخت عرض برمبلی، تعداد هادیفر، ضرب دکارتی، محصول قوی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Two lower bounds for the treewidth of product graphs are presented in terms of the bramble number. The first bound is that the bramble number of the Cartesian product of graphs G1 and G2 must be at least the product of the Hadwiger number of G1 and the PI number of G2, where the PI number is a new graph parameter introduced in this paper. The second bound is that the bramble number of the strong product of graphs G1 and G2 must be at least the product of the Hadwiger number of G1 and the bramble number of G2. We also demonstrate applications of the lower bounds.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 251-258
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 251-258
نویسندگان
Kyohei Kozawa, Yota Otachi, Koichi Yamazaki,