论文部分内容阅读
图论是数学的一个分支,尤其是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学以及在计算机科学中有着很广泛的应用.它最吸引人的特色是它蕴涵着大量强有力的思想、漂亮的图形和巧妙的论证,而它解决问题的方法也是千变万化,非常灵活,所以解决图论中的问题不仅需要知识,而且更需要智慧和灵活深入的思考.
k-超竞赛图是图论中的一个很有趣的研究课题,是一般竞赛图的推广,有着较好的研究价值和较实际的应用前景.早在很久之前外国的一些著名学者如,Barbut,Bialostcki以及Frankl就对超竞赛图做了一定的研究,并且他们也提出了一个重要的结论:每一个竞赛图都有一个Hamilton路,每一个强竞赛图都有一个Hamilton圈.Bondy也通过超竞赛图与Hamilton路之间的关系解决了用一次循环赛所得的得分序列决定名次的问题.在1953年社会学家Landau也通过超竞赛图研究了小鸡与小鸡之间统治与啄咬次序之间的关系.
周国飞,张克民对k-超竞赛图的度序列做了相应的研究,设k=3,n>3,S=(s1,s2,…,si)为非降的非负整数序列,则S为某一个3-超竞赛图的度序列当且仅当:对任意的r(1≤r≤n),有∑si≥(r2)(n-2,k-2),且当r=n时取等号.并提出了猜想:设k≥4,n>k,S=(s1,s2,…,si)为非降的非负整数序列,则S为某一个k-超竞赛图的度序列当且仅当:对任意的r(1≤r≤n),有∑si≥(r2)(n-2,k-2),且当r=n时取等号.
在2004年,王超,周国飞又对猜想中k=4的情况给出了相应的证明.本文在此基础上继续研究此猜想的成立,证明了当k=5时结论依然成立.