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

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
نویسندگان
, , , ,