>
Fa   |   Ar   |   En
   majorization and the number of bipartite graphs for given vertex degrees  
   
نویسنده berger annabell
منبع transactions on combinatorics - 2018 - دوره : 7 - شماره : 1 - صفحه:19 -30
چکیده    The emph{bipartite realisation problem} asks for a pair of nonnegative‎, ‎non-increasing integer lists $a:=(a_1,ldots,a_n)$ and $b:=(b_1,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 galeryser 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=1}^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.
آدرس martin-luther university of halle-wittenberg, department of computer science, germany
پست الکترونیکی berger@informatik.uni-halle.de
 
     
   
Authors
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved