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

Generalization of Characterization Theorem on Interval Bigraphic Sequences

作　　者：郭纪云[1] 蔡白光[1] 

机构地区：[1]海南大学信息科学技术学院,海南海口570228

出　　处：《长沙大学学报》2016年第2期4-5,共2页Journal of Changsha University

基　　金：海南省自然科学基金资助项目(批准号:20151004;114001)

摘　　要：设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-二部图.Let Pm= p1,…,pmand Qn= q1,…,qnbe two non- increasing sequences of nonnegative integers. The pair（ Pm,Qn） is said to be bigraphic if there is a simple X,Y- bigraph G such that the vertices of X have degrees p1,…,pmand the vertices of Y have degrees q1,…,qn. In this case,G is called a realization of（ Pm,Qn）. The pair（ Pm,Qn） is said to be t- bigraphic if it is bigraphic and no two vertices from different partite sets are joined by more than t edges. In this case,the realization of（ Pm,Qn） is called a t- bigraph. Gale and Ryser presented a classical characterization theorem on bigraphic sequences. Garg et al. considered interval bigraphic sequences,and gave a corresponding characterization theorem. In this paper,we generalize Garg＇s characterization theorem from 1-graph to t- graph.

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

分 类 号：O157.5[理学—数学]