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

郭纪云，蔡白光

(海南大学信息科学技术学院, 海南 海口 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])是两个由非负整数构成的区间序列, 其中a1≥…≥am且c1≥…≥cn, 则存在一个t-二部图G,其部集为X={x1,…,xm}和Y={y1,…,yn}, 使得ai≤dG(xi)≤bi,1≤i≤m且cj≤dG(yj)≤dj,1≤j≤n当前且仅当对于每一个整数k1,1≤k1≤m,有

(1)

且对于每一个整数k2,1≤k2≤n,有

(2)

2定理1.2的证明

必要性. 设G是满足条件的t-二部图, 其部集为X={x1,…,xm}和Y={y1,…,yn}.考虑关联到X中的k1个顶点的所有边. 由于G是t-二部图, 因此每个yj∈Y最多关联到这些边中的tk1条, 而且yj也最多关联到这些边中的dG(yj)条. 于是, 对于每一个整数k1,1≤k1≤m, 有

因此(1)式成立. 同理可证(2)式亦成立.

情形(1)对于某个j和k(k>r), e(yj,xk)≥1, 且存在某个l(l≤r)使得e(yj,xl)e(v,xr).

情形(2)对于某个j和l(l≤r), d(yj)e(v,xr).

若以上两种情形均不能应用, 则

(3)

因为d(xi)=ai,1≤i

在G′中, 定义一个临界指标s, 它是满足条件d(yj)≥cj,1≤j

情形(3)对于某个i(ie(v,ys).

若以上三种情形均不能应用, 则类似于(3)式, 可得d(ys)=cs. 令s的值增加1, 重复上述步骤, 可构造出想要的t-二部图.

参考文献：

[1] Gale D. A theorem on flows in networks[J]. Pacific Journal of Mathematics,1957,(2):1073-1082.

[2] Ryser H J. Combinatorial properties of matrices of zeros and ones[J]. Canadian Journal of Mathematics, 1957, (9):371-377.

[3] Garg A, Goel A, Tripathi A. Constructive extensions of two results on graphic sequences[J]. Discrete Mathematics,2011,(17):2170-2174.

(责任编校：晴川)

Generalization of Characterization Theorem on Interval Bigraphic Sequences

GUO Jiyun, CAI Baiguang

(College of Information Science and Technology, Hainan University, Haikou Hainan 570228, China)

Abstract：Let Pm=p1,…,pm and Qn=q1,…,qn be 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,…,pm and 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.

Key Words：bigraphic sequence; interval bigraphic sequence;t-bigraphic sequence

中图分类号:O157.5

文献标识码：A

文章编号：1008-4681(2016)02-0004-02

作者简介：郭纪云(1984— ),女,山东菏泽人,海南大学信息科学技术学院讲师,硕士.研究方向:图论及其应用.

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

收稿日期：2016-03-07