二部图的二部劈性与蕴含A-连通二部可图序列

发布时间：2020-05-23 17:02

【摘要】：若一个二部图的顶点集可以被划分为一个完全二部集和一个独立集,则称这个二部图是一个二部劈图。一个二部图的二部劈性是指在这个二部图中添加或者删去的最少的边数,从而形成一个二部劈图。本文中,我们证明了一个二部图的二部劈性只与二部图的度序列对有关,并且给出了求二部劈性的一个简便计算公式。作为推论,我们对二部劈图的度序列对进行了简单的刻划。设S =(a1,...,am;,b1,...,bn)是一个序列对,其中a1,...,am和b1,...,bn是两个非增非负整数序列。若序列对S=(a1,...,,am;b1...,bn)是某个简单二部图G =(X∪Y,E)的度序列对,使得部分集X和Y中各顶点的度分别为a1,...,am和b1,...,bn,则称该序列对是一个二部可图对。设A是一个阿贝尔(加法)群,我们定义σ(A,m,n)是最小的整数k,使得每一个二部可图对S =(a1,...,am;b1,...,bn)满足当am,bn≥2且σ(S)=a1+…+am≥k时,有一个A-连通实现。在本文中,我们确定了当|A|=k≥ 5且m≥n≥2时,σ(A,m,n)之值。
【学位授予单位】：海南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】