区间上二部可图序列刻划定理的推广

设Pm=p1,…,pm及Qn=q1,…,qn是两个由非负整数构成的不增序列.如果存在一个简单X,Y-二部图G使得X中的顶点的度分别为p1,…,pm且Y中的顶点的度分别为q1,…,qn,那么称序列对(Pm,Qn)是二部可图的,并称二部图G为(Pm,Qn)的一个实现.如果(Pm,Qn)二部可图且任何两个来自不同部集的顶点之间最多关联t条边,那么称(Pm,Qn)是t-二部可图的,并称(Pm,Qn)的实现为t-二部图.Gale和Ryser分别独立地给出了关于二部可图序列的刻划定理.Garg等人考虑了区间上的二部可图序列,并给出相应刻划.此研究将其刻划由1-二部推广至图t-二部图.

Gale-Ryser型刻划定理的一个推广

设Pm= p1,…,Pm及Qn=q1,…,qn 是两个由非负整数构成的不增序列。如果存在一个简单X,Y-二部图使得X中的顶点的度分别为 且Y中的顶点的度分别为 ,那么称序列对 是二部可图的。如果二部可图且任何两个来自不同部集的顶点之间最多连有t条边,那么称是t-二部可图的。本文给出一个t-二部可图序列的刻划定理。事实上,该定理是Gale-Ryser型刻划定理的一个推广。