首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Minimum congestion spanning trees in bipartite and random graphs
Authors:MI Ostrovskii
Institution:Department of Mathematics and Computer Science, St. John's University, 8000 Utopia Parkway, Queens, NY 11439, USA
Abstract: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 n 3 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 n 3 2 .
Keywords:Bipartite graph  random graph  minimum  congestion spanning tree
本文献已被 CNKI 维普 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号