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. 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. 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

期刊菜单