کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9515483 1343458 2005 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A family of bijections between G-parking functions and spanning trees
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A family of bijections between G-parking functions and spanning trees
چکیده انگلیسی
For a directed graph G on vertices {0,1,…,n}, a G-parking function is an n-tuple (b1,…,bn) of non-negative integers such that, for every non-empty subset U⊆{1,…,n}, there exists a vertex j∈U for which there are more than bj edges going from j to G-U. We construct a family of bijective maps between the set PG of G-parking functions and the set TG of spanning trees of G rooted at 0, thus providing a combinatorial proof of |PG|=|TG|.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 110, Issue 1, April 2005, Pages 31-41
نویسندگان
, ,