Majorization and the number of bipartite graphs for given vertex degrees
محل انتشار: فصلنامه معادلات در ترکیبات، دوره: 7، شماره: 1
سال انتشار: 1397
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 82
فایل این مقاله در 12 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_COMB-7-1_003
تاریخ نمایه سازی: 17 آبان 1400
چکیده مقاله:
The \emph{bipartite realisation problem} asks for a pair of non-negative, non-increasing integer lists a:=(a_۱,\ldots,a_n) and b:=(b_۱,\ldots,b_{n'}) if there is a labeled bipartite graph G(U,V,E) (no loops or multiple edges) such that each vertex u_i \in U has degree a_i and each vertex v_i \in V degree b_i. The Gale-Ryser theorem provides characterisations for the existence of a `realisation' G(U,V,E) that are strongly related to the concept of \emph{majorisation}. We prove a generalisation; list pair (a,b) has more realisations than (a',b), if a' majorises a. Furthermore, we give explicitly list pairs which possess the largest number of realisations under all (a,b) with fixed n, n' and m:=\sum_{i=۱}^n a_i. We introduce the notion~\emph{minconvex list pairs} for them. If n and n' divide m, minconvex list pairs turn in the special case of two constant lists a=(\frac{m}{n},\ldots,\frac{m}{n}) and b=(\frac{m}{n'},\ldots,\frac{m}{n'}).
کلیدواژه ها:
bigraphic sequence ، matrices with fixed row and column sums ، contingency tables with fixed margins ، bipartite realisation problem ، Gale-Ryser theorem
نویسندگان
Annabell Berger
Department of Computer Science Martin-Luther University Halle-Wittenberg
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :