An extension of a result of Alon, Ben-Shimon and Krivelevich on bipartite graph vertex sequences

详细信息    查看全文

• 作者：Lei Meng ; Jian-Hua Yin ; ^{yinjh@ustc.edu}
• 关键词：Bipartite graph ; Degree sequences ; Bigraphic pairs
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：340
• 期：4
• 页码：572-577
• 全文大小：372 K
• 卷排序：340

文摘

Let S=(a1,…,am;b1,…,bn)S=(a1,…,am;b1,…,bn) be a pair of two nonincreasing sequences of positive integers, that is, a1,…,ama1,…,am and b1,…,bnb1,…,bn are two nonincreasing sequences of positive integers. The pair S=(a1,…,am;b1,…,bn)S=(a1,…,am;b1,…,bn) is said to be a bigraphic pair   if there is a simple bipartite graph G=(X∪Y,E)G=(X∪Y,E) such that a1,…,ama1,…,am and b1,…,bnb1,…,bn are the degrees of the vertices in XX and YY, respectively. In this paper, we give a simple sufficient condition for a pair S=(a1,…,am;b1,…,bn)S=(a1,…,am;b1,…,bn) to be a bigraphic pair. The condition depends only on the lengths of two sequences of the pair and their largest and smallest elements. This result extends a result due to Alon et al. (2010).