Kotzig有向图的度偶序列

1.引言 设T_n是n阶竞赛图,V={v_1,v_2,…,v_n}是T_n的顶点集合。设扩v∈V,T_n中所有被v占优的顶点个数s(v)是v在T_n中的得分,记s(v_i)=s_i,i=1,2,…,n.将v_1,v_2,…,v_n重新排列,使s_1≤s_2≤…≤s_n,则S=(s_1,s_2,…,s_n)即是T_n的得分向量。 在Bondy与Murty的名著《图论及其应用》一书的末尾处列举了50个图论中未解决的问题,其中第45问题是:刻划所有n-1阶子竞赛图都同构的n阶竞赛图。这个问题是Kotzig 1973年提出的(见[1])。作者、黄国勋与林毓材研究了这个问题。