کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4664245 1345290 2011 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum congestion spanning trees in bipartite and random graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات (عمومی)
پیش نمایش صفحه اول مقاله
Minimum congestion spanning trees in bipartite and random graphs
چکیده انگلیسی

The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Acta Mathematica Scientia - Volume 31, Issue 2, March 2011, Pages 634-640