【作者】 白彩虹；

【导师】 李胜家；

【作者基本信息】 山西大学 ， 应用数学， 2012， 硕士

【摘要】 一个竞赛图是任何两个顶点均相邻的定向图.称有向图D是泛圈的,如果它包含从3到|V(D)|的每个长度的圈.称有向图D的一条弧是k泛的,如果它属于每个l-圈(k≤l≤|V(D)|).当k=3时,也称该弧是泛圈的.称有向图D中的顶点u是外弧泛圈点,如果它的每条外弧是泛圈的.本文主要研究强连通竞赛图中的外弧4泛圈点问题.在2000年,Yao等人首先提出并证明了每一个强连通竞赛图存在一点u使得u的每条外弧都是泛圈的.在2005年,Yeo证明了每一个3-强连通竞赛图中存在两个不相同的顶点x,y使得x与y的所有外弧都是泛圈的.在2006年,李瑞娟等人又证明了每个k强连通竞赛图至少包含k+1个外弧4泛圈点.在2010年,郭巧萍等人证明了每个k强连通竞赛图至少包含k+2个外弧5泛圈点.文章在前人的基础上主要讨论了2-强连通竞赛图和k(k≥3)-强连通竞赛图中的外弧4泛圈点的问题.本文主要分为四章.第一章是预备知识,我们介绍了一些本文中将要用到的图论方面的基本概念和记号.第二章回顾了竞赛图中相关的一些结果.第三章,我们研究了2-强连通竞赛图中的外弧4泛圈点问题,主要结果如下：设T是一个δ+(T)≥3的2-强连通竞赛图,M是T中外度最小的点的集合.若|M|≠3且对任意v∈M有σ(T-v)=2,则T中至少有四个外弧4泛圈点.第四章,我们研究了k(k≥3)-强连通竞赛图中的外弧4泛圈点问题,主要结果如下：设T是一个k(k≥3)-强连通竞赛图.若δ+(T)≥k+1,则T中至少有k+2个外弧4泛圈点.更多还原

【Abstract】 A tournament is an oriented graph where every pair of distinct vertices are adjacent. A digraph D is called to be pancyclic, if it contains a cycle of length from3to|V(D)|. An arc is said to be k-pancyclic in a digraph D, if it belongs to an l-cycle for all k≤l≤|V(D)|. For k=3, we also say that the arc is pancyclic. We call a vertex u of digraph D is out-arcs pancyclic vertex, if each out-arcs of u is pancyclic. In2000, Yao et al. brought up and proved that every strong tournament contains a vertex u such that every out-arc of u is pancyclic. In2005, Yeo proved that every3-strong tournament contains two distinct vertices x and y, such that all arcs out of x and all arcs out of y are pancyclic. In2006, Li Ruijuan et al. gave the results that every k-strong tournament contains at least k+1out-arc4-pancyclic vertices, and Guo Qiaoping et al. proved that every k-strong tournament contains at least k+2distinct vertices whose out-arcs are pancyclic in2010. In this paper, the problems of out-arcs4-pancyclic vertices in2-strong tournaments and k(k≥3)-strong tournaments are discussed on the basis of predecessor.This paper is composed of four chapters. In the first chapter, we introduce some useful basic concepts and marks which will be used in the paper.In the second chapter, we review some known results on tournaments.In the third chapter, we study the problem of out-arcs4-pancyclic vertices in2-strong tournaments. The main results as follows:Let T be a2-strong tournament with δ+(T)≥3, and let M be the set of minimum out-degree vertices in V(T). If|M|≠3and σ(T-v)=2for any v∈M, then there exist at least four out-arcs4-pancyclic vertices.In the fourth chapter, we study the problem of out-arcs4-pancyclic vertices in k(k≥3)-strong tournaments. We prove that:If T is a k(k≥3)-strong tournament with δ+(T)≥k+1, then there exist at least k+2out-arcs4-pancyclic vertices.更多还原