Article ID Journal Published Year Pages File Type
4648373 Discrete Mathematics 2009 5 Pages PDF
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
,