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

作者：Meng, Lei; Yin, Jian-Hua^*

来源：Discrete Mathematics, 2017, 340(4): 572-577.

DOI：10.1016/j.disc.2016.12.002

• Bipartite graph
• Degree sequences
• Bigraphic pairs

Let S = (a(1),.., a(m); b(1),..., b(n)) be a pair of two nonincreasing sequences of positive integers, that is, a(1),..., a(m) and b(1),..., b(n) are two nonincreasing sequences of positive integers. The pair S = (a(1),..., a(m); b(1),..., b(n).) is said to be a bigraphic pair if there is a simple bipartite graph G = (X boolean OR Y, E) such that a(1),..., a(m) and b(1),..., b(n) are the degrees of the vertices in X and Y, respectively. In this paper, we give a simple sufficient condition for a pair S = (a(1),..., a(m); b(1),..., b(n)) 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).

• 出版日期2017-4
• 单位海南大学