论文部分内容阅读
假定D是一个无环有向略，D的竞争图是指一个与D有相同的顶点集的无向图，满足在这个无向略中顶点u和顶点v之间有一个条边当且仅当存在一个顶点x∈D使得(u,x),(u,x)是D中的弧.图G的竞争数是指满足在G中加入k个孤立点是某个无环有向图的竞争图的k的最小值，记作k(G).对于任意的图G，一般情况下计算出它的竞争数k(G)是非常困难的.本文中，我们给出了关于完全四部图Kn,n,n,n的竞争数的一些结论。