度条件下的二部图的定向图

摘要：

二部图是具有二分类(X,Y)的简单偶图,其中X的每个顶点与Y的每个顶点相连,若|X|=m,|Y|=n,则这样的图记为Km,n.该文研究了Kn,n的定向图.对于非负整数a和b,若存在满足每个顶点的入度或者是a或者是b的一个Kn,n的定向图,则存在非负整数s和t满足方程s+t=2n和as+bt=n2.论文证明了如下结论:设s和t是任意两个非负整数,对于满足方程s+t=2n和as+bt=n2的非负整数a和b,存在Kn,n的定向图使得每个顶点的入度或者是a或者是b,从而得到了上述必要条件为Kn,n是[a,b]n可实现的充分条件.

关键词：完全二部图、定向、入度、算法

所属期刊栏目：34

分类号：O157.6(代数、数论、组合理论)

资助基金：陆军装甲兵学院科研创新基金2016CJ012016CJ0103

在线出版日期：2019-06-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：239-252