کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647677 1342366 2013 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Realizing degree sequences with kk-edge-connected uniform hypergraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Realizing degree sequences with kk-edge-connected uniform hypergraphs
چکیده انگلیسی

An integral sequence d=(d1,d2,…,dn)d=(d1,d2,…,dn) is hypergraphic if there is a simple hypergraph HH with degree sequence dd, and such a hypergraph HH is a realization of dd. A sequence dd is rr-uniform hypergraphic if there is a simple rr-uniform hypergraph with degree sequence dd. Similarly, a sequence dd is rr-uniform multi-hypergraphic if there is an rr-uniform hypergraph (possibly with multiple edges) with degree sequence dd. In this paper, it is proved that an rr-uniform hypergraphic sequence d=(d1,d2,…,dn)d=(d1,d2,…,dn) has a kk-edge-connected realization if and only if both di≥kdi≥k for i=1,2,…,ni=1,2,…,n and ∑i=1ndi≥r(n−1)r−1, which generalizes the formal result of Edmonds for graphs and that of Boonyasombat for hypergraphs. It is also proved that a nonincreasing integral sequence d=(d1,d2,…,dn)d=(d1,d2,…,dn) is the degree sequence of a kk-edge-connected rr-uniform hypergraph (possibly with multiple edges) if and only if ∑i=1ndi is a multiple of rr, dn≥kdn≥k and ∑i=1ndi≥max{r(n−1)r−1,rd1}.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 12, 28 June 2013, Pages 1394–1400
نویسندگان
, ,