کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648373 1632440 2009 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Spanning tree congestion of the hypercube
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Spanning tree congestion of the hypercube
چکیده انگلیسی

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).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issues 23–24, 6 December 2009, Pages 6644–6648
نویسندگان
,