郭纪云，蔡白光

(海南大学信息科学技术学院, 海南 海口 570228)



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

郭纪云，蔡白光

(海南大学信息科学技术学院, 海南 海口 570228)

摘要：设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-二部图.

关键词：二部可图序列；区间上二部可图序列； t-二部可图序列

1相关知识

设Pm=p1,…,pm及Qn=q1,…,qn是两个由非负整数构成的不增序列. 如果存在一个简单X,Y-二部图G使得X中的顶点的度分别为p1,…,pm且Y中的顶点的度分别为q1,…,qn，那么称序列对(Pm,Qn)是二部可图的, 并称二部图G为(Pm,Qn)的一个实现. Gale[1]和Ryser[2]分别给出了经典的关于二部可图序列的刻划定理.Garg等人[3]则考虑了区间上的二部可图序列，并给出如下定理.

称由非负整数构成的不增序列对(Pm,Qn)是t-二部可图的, 如果(Pm,Qn)二部可图且任何两个来自不同部集的顶点之间最多关联t条边. 此时, (Pm,Qn)的实现称为t-二部图.本文给出一个区间上t-二部可图序列刻划定理, 从而将区间上二部可图序列的刻划从1-图推广至t-图.

定理1.2设L1=([a1,b1],…,[am,bm])和L2=([c1,d1],…,[cn,dn])是两个由非负整数构成的区……