کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648167 | 1342395 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Spanning tree congestion of kk-outerplanar graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In 1987, Simonson conjectured that every kk-outerplanar graph of maximum degree dd has spanning tree congestion at most k⋅dk⋅d [S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20 (1987) 235–252]. We show that his conjecture is true and the bound is tight for outerplanar graphs and kk-outerplanar graphs of maximum degree 4. We give a precise characterization of the spanning tree congestion of outerplanar graphs, and thus show that the spanning tree congestion of outerplanar graphs can be determined in linear time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 12, 28 June 2011, Pages 1040–1045
Journal: Discrete Mathematics - Volume 311, Issue 12, 28 June 2011, Pages 1040–1045
نویسندگان
Hans L. Bodlaender, Kyohei Kozawa, Takayoshi Matsushima, Yota Otachi,