摘要
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])。作者、黄国勋与林毓材研究了这个问题。
We say that a digraph G of order n is a Kotzig digraph if all its induced suhdigraphs of order n-l are isomorphic,and that a sequence D of pairs of non-negative integers is a degreepair sequence with realizitions by the Kotzig digraphs if it is a degree-pair sequence of some Kotzig digraph.The object of this paper is to give the necessary and sufficient conditions for determining whether a sequence of pairs of non-negative integers to be a degree-pair sequence with realizitions by the Kotzig digraphs.We also discuss a similar problem for the undirected graphs.
出处
《应用数学学报》
CSCD
北大核心
1991年第3期384-390,共7页
Acta Mathematicae Applicatae Sinica
