Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648373 | Discrete Mathematics | 2009 | 5 Pages |
Abstract
Let GG be a finite connected graph and TT be a spanning tree. For any edge ee of TT, let Ae,BeAe,Be be the components of T∖eT∖e. The edge congestion of ee in TT is defined as ecG(e,T)=|{uv∣u∈Ae,v∈Be}|ecG(e,T)=|{uv∣u∈Ae,v∈Be}|, and the congestion of TT is the maximum of ecG(e,T)ecG(e,T) over all edges of TT. Then the spanning tree congestion s(G)s(G) of GG is the minimum of congestion over all spanning trees of GG. Hruska [S.W. Hruska, On tree congestion of graphs, Discrete Math. 308 (2008) 1801–1809] conjectured that for the hypercube QdQd, s(Qd)=2d−1s(Qd)=2d−1. We disprove the conjecture and show that s(Qd)=Θ(log2dd2d).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hiu-Fai Law,