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

作者：张雪飞; 郑素文; 夏静; 曹贻鹏; 许飞

来源：高校应用数学学报A辑(中文版), 2019, 34(02): 239-252.

DOI：10.13299/j.cnki.amjcu.002077

• 完全二部图
• 定向
• 入度
• 算法

二部图是具有二分类(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可实现的充分条件.

• 单位
  中国人民解放军装甲兵工程学院