完全分割图的最小直径定向

摘要

对于图G,记G的具有最小直径的定向图为G′.用K2[Kn,m]表示由阶为n的团和阶为m的独立集构成的完全分割图.为了得到完全分割图K2[Kn,m]的最小直径定向,首先给出Kn的一个定向Rn使得diam(Rn)=2,然后对Kn与K-m之间的边也给出特殊的定向.并证明了下述结论:diam(K′2[Kn,K-m])=3, m> (n)/((n)/(2) ),2, m≤ (n)/( (n)/(2) )-n.