关于二部可图序列和蕴含P-可图序列的研究

发布时间：2018-11-26 20:16

【摘要】：设S =(a_1,...,a_m;b_1,…,b_n)是一个序列对,其中a_1,...,a_m和b_1,...,b_n是非增非负整数序列。若序列对S是某个简单二部图G =(X∪Y,E)的度序列,使得顶点集X和Y中各顶点的度分别为a_1,...,a_m和b1,...,bn,则称S是一个二部可图序列,并称G为S的一个实现。在本文中,我们给出了一个简单的充分条件使得S=(a_1,...,a_m;b1,...,bn)是二部可图的。这个条件只依赖于S的长度和其最大值与最小值。这个结果推广了Alon,Ben-Shimon和Krivelevich(J.Graph Theory,64(3)(2010)244-249)的结果。若非增非负整数序列π =(d_1,...,d_n)是某个n阶简单图G的度序列,则称π是一个可图序列,并称G为π的一个实现。设G是一个连通图,我们称|E|-|V|+ 1为G的圈数,记做c(G)。如果c(G)= 1,2,和3,我们分别称G是1圈图,2圈图和3圈图。在本文中,我们给出了一个充要条件使得π=(d_1,...,d_n)有一个实现G具有c(G)= k。设π=(d_1,...,d_n)是一个可图序列,且G是π的一个实现。如果G包含一个r阶3正则图作为子图,则称π是蕴含Pr3-可图的。在本文中,我们还探索了π是蕴含Pr3-可图的充要条件。
[Abstract]:Let S = (a _ B _ S _ n) is a sequence pair in which a _ If the sequence pair S is a degree sequence of some simple bipartite graph G = (X 鈪，

本文编号：2359519