强连通多部竞赛图中的泛圈性研究

项目名称： 强连通多部竞赛图中的泛圈性研究

项目编号： No.11201273

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 郭巧萍

作者单位： 山西大学

项目金额： 22万元

中文摘要： 图的泛圈性问题是Hamilton问题的自然推广。近年来，图的泛圈性问题已经成为图论中一个重要研究课题。竞赛图是有向图中结构最好的一类图，其泛圈性方面已有很多结果。多部竞赛图作为竞赛图的自然推广，也作为有向图中的一个非常重要的图类，也受到了广泛的关注，但其泛圈性方面的结果却很少。一般来说，多部竞赛图不是泛圈的，更不是顶点泛圈的。对多部竞赛图的泛圈性问题的研究，几乎集中在正则和几乎正则多部竞赛图中。本项目将主要研究强连通多部竞赛图的圈与一些参数，如部集数、连通度、独立数、最小度、最大度、全局非正则度、局部非正则度等指标之间的联系，进而获得强连通多部竞赛图泛圈、顶点泛圈以及它包含泛弧、外弧泛圈顶点的若干条件，并试图证明Yeo在1999年提出的一个猜想: "每个正则4-部竞赛图是顶点泛圈的"和Volkmann在2002年提出的猜想："几乎正则4-部竞赛图是顶点4泛的"。

中文关键词： 多部竞赛图；泛圈性；圈；外路；

英文摘要： The pancyclicity problem of graphs is the natural generalization of the Hamilton problem. In recent years, the pancyclicity problem of graphs has been an important topic in graph theory. Tournaments are the best structure class of directed graphs and there are many results on its pancyclicity. Multipartite tournaments, as the natural generalization of tournaments and as a class of very important digraphs, have been get extensive attention. However, the results on pancyclicity in multipartite tournaments are still very few. In general, multipartite tournaments are not pancyclic, and nor vertex pancyclic. The discuss for pancyclicity of multipartite tournaments has focused almost entirely in regular and almost regular multipartite tournaments. In this item, we will mainly research the relation between cycles and some parameters of strong multipartite tournaments, such as the number of partite sets、connectivity、independence number、minimum degree、maximum degree、global irregularity、local irregularity and so on, and then obtain some conditions for strong multipartite tournaments to be pancyclic、vertex- pancyclic and to contain pancyclic arcs、 out-arc pancyclic vertices. In addition, we will try to prove the conjecture posed by Yeo in 1999 " Each regular 4-partite tournament is vertex-pancyclic" and the conjecture pose

英文关键词： Multipartite tournament；Pancyclicity；Cycle；Outpath；