Acta mathematica scientia, Series B >
MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS
Received date: 2007-09-15
Revised date: 2009-03-09
Online published: 2011-03-20
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.
Key words： Bipartite graph; random graph; minimum congestion spanning tree
M.I.Ostrovskii . MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS[J]. Acta mathematica scientia, Series B, 2011 , 31(2) : 634 -640 . DOI: 10.1016/S0252-9602(11)60263-4
[1] Bollobás B. Modern Graph Theory. New York: Springer-Verlag, 1998
[2] Ostrovskii M I. Minimal congestion trees. Discrete Math, 2004, 285: 219--226
[3] Ostrovskii M I. Sobolev spaces on graphs. Quaestiones Mathematicae, 2005, 28: 501--523
[4] Wu B Y, Chao K M. Spanning trees and optimization problems. Boca Raton: Chapman & Hall/CRC, 2004
[5] Asratian A S, Denley T M J, Häggkvist P. Bipartite graphs and their applications. Cambridge: Cambridge University Press, 1998
[6] Jordan C. Sur les assemblages de lignes. J Reine Angew Math, 1869, 70: 185--190
[7] Harary F. Graph Theory. London: Addison-Wesley Publishing Company, 1969
[8] Janson S, L uczak T, Ruci\'nski A. Random graphs. New York: Wiley, 2000
[9] Bollobáas B, Thomason A. Random graphs of small order//Karo\'nski M, Ruci\'nski A eds. Random Graphs `83. Amsterdam: North-Holland, 1985: 47--97
[10] Bollobàs B. Random graphs. London: Academic Press, 1985
/
| 〈 |
|
〉 |