Advances in Applied Mathematics
Vol.05 No.01(2016), Article ID:17015,3
pages
10.12677/AAM.2016.51016
A Generalization of the Gale-Ryser Type Characterization Theorem
Jiyun Guo, Dongmei Wang
College of Information Science and Technology, Hainan University, Hainan Haikou
Received: Feb. 4th, 2016; accepted: Feb. 19th, 2016; published: Feb. 26th, 2016
Copyright © 2016 by authors and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
ABSTRACT
Let and
be two non-increasing sequences of nonnegative integers. The pair
is said to be bigraphic if there is a simple X,Y-bigraph such that the vertices of X have degrees
and the vertices of Y have degrees
.
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 paper, we give a characterization for
to be t-bigraphic. In fact, it is a generation of the Gale-Ryser type characterization theorem.
Keywords:Degree, Bigraphic Sequence, t-Bigraphic Sequence
Gale-Ryser型刻划定理的一个推广
郭纪云,王冬梅
海南大学信息科学技术学院,海南 海口
收稿日期:2016年2月4日;录用日期:2016年2月19日;发布日期:2016年2月26日
摘 要
设及
是两个由非负整数构成的不增序列。如果存在一个简单X,Y-二部图使得
中的顶点的度分别为
且
中的顶点的度分别为
,那么称序列对
是二部可图的。如果
二部可图且任何两个来自不同部集的顶点之间最多连有t条边,那么称
是t-二部可图的。本文给出一个t-二部可图序列的刻划定理。事实上,该定理是Gale-Ryser型刻划定理的一个推广。
关键词 :度,二部可图序列,t-二部可图序列
1. 引言
设及
是两个由非负整数构成的不增序列。如果存在一个简单
-二部图使得
中的顶点的度分别为
且
中的顶点的度分别为
,那么称序列对
是二部可图的。以下是著名的Gale-Ryser型关于二部可图序列的刻划定理。
定理1 (Gale [1] , Ryser [2] )设及
是两个由非负整数构成的不增序列且满足条件
,则序列对
是二部可图的当且仅当对于任意的整数
,
,有
如果二部可图且任何两个来自不同部集的顶点之间最多连有t条边,其中t是正整数,那么称
是t-二部可图的。本文给出一个t-二部可图序列的刻划定理。事实上,该定理是Gale-Ryser型刻划定理的一个推广,当
时下面的定理2即为定理1。
定理2 设及
是两个由非负整数构成的不增序列且它们满足条件
,则序列对
是t-二部可图的当且仅当对于任意的整数
,
,有
(1)
2. 定理2的证明
必要性。设是实现
的一个t-二部图,其部集为
和
。考虑关联到
中的
个顶点的所有边。由于
是t-二部图,因此每个
最多关联到这些边中的
条,而且
也最多关联到这些边中的
条。于是,
是关联到
的任意
个顶点的所有边的条数的上界,这个界在度为
的那些顶点上取得。
充分性。设有两个非增非负整数序列及
,它们满足(1)式。首先,我们构造一个t-二部图
,其部集
和
满足条件
及
。定义一个临界指标
,它是满足条件
且
的最大的下标。我们将逐步去掉顶点
处的差额
而保持
及
。我们从
个顶点的空图开始,此时
,除非对于所有的
都有
,在这种情况下结论已成立。为了方便,记
为顶点
与
之间的边所构成的集合,
。对于顶点
,由于
,因此一定存在顶点
使得
。
情形(1) 对于某个和
,
,且存在某个
使得
。当
时,在顶点
与
之间去掉一条边,在
与
之间连上一条边。当
时,分别在
与
,
与
之间去掉一条边,分别在
与
,
与
之间连上一条边,其中
。
情形(2) 对于某个和
,
且
。当
时,在
与
之间连上一条边。当
时,在
与
之间去掉一条边,分别在
与
,
与
之间连上一条边,其中
。
若以上两种情形均不能应用,则
由(1)知,又
,故
。重复上述步骤可得到图
,满足
且
。又因为
,从而有
。因此
就是想要的t-二部图,即
是t-二部可图的。
基金项目
海南省自然科学基金资助项目(20151004)。
文章引用
郭纪云,王冬梅. Gale-Ryser型刻划定理的一个推广
A Generalization of the Gale-Ryser Type Characterization Theorem[J]. 应用数学进展, 2016, 05(01): 121-123. http://dx.doi.org/10.12677/AAM.2016.51016
参考文献 (References)
- 1. Gale, D. (1957) A Theorem on Flows in Networks. Pacific Journal of Mathematics, 7, 1073-1082. http://dx.doi.org/10.2140/pjm.1957.7.1073
- 2. Ryser, H.J. (1957) Combinatorial Properties of Matrices of Zeros and Ones. Canada Journal of Mathematics, 9, 371-377. http://dx.doi.org/10.4153/CJM-1957-044-3