强竞赛图的外弧4泛圈点问题
摘要
一个竞赛图是任何两个顶点均相邻的定向图.称有向图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泛圈点.
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.
本文主要分为四章.第一章是预备知识,我们介绍了一些本文中将要用到的图论方面的基本概念和记号.
第二章回顾了竞赛图中相关的一些结果.
第三章,我们研究了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泛圈点.
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.
引文
[1]Bang-Jensen J. and Gutin G. Digraph:Theory, Algorithms and Applications[M]. Springer, London,2000.
[2]Bondy J A and Murty U S R. Graph Theory[M]. Springer, New York, 2008.
[3]Yao T, Guo Y and Zhang K. Pancyclic out-arcs of a vertex in a tournament[J]. Discrete Appl. Math.,2000,99:245-249.
[4]Yeo A. The number of pancyclic arcs in a k-strong tournament[J]. Journal of Graph Theory, 2005,50: 212-219.
[5]Li R, Li S and Feng J. The number of vertices whose out-arcs are pancyclic in a 2-strong tournament[J]. Discrete Appl. Math.,2008,156:88-92.
[6]Feng J. Each 3-strong tournament contains 3 vertices whose out-arcs are pancyclic[J]. Graphs Combin.,2009,25:299-307.
[7]Guo Q, Li S, Guo Y and Li H. Out-arc pancyclicity of vertices in tournaments[J]. Discrete Applied Mathematics,2010,158:996-1005.
[8]Redei L. Ein kombinatorischer Satz[J]. Acta Litt. Sci. Szeged,1934,7: 39-43.
[9]Camion P. Chemins et circuits hamiltoniens des graphes complets[J]. C. R. Acad. Sci. Paris,1959,249:2151-2152.
[10]Harary F and Moser L. The theory of round robin tournaments[J]. Amer. Math. Monthly, 1966,73:231-246.
[11]Moon J W. On subtournaments of a tournament[J]. Canad. Math. Bull.,1966,9: 297-301.
[12]Alspach B. Cycles of each length in regular tournament[J]. Canad. Math. Bull., 1967,10:283-286.
[13]Wu Z, Zhang K and Zou Y. A necessary and sufficient condition for arc-pancyclicity of tournaments[J]. Sci. Sinica, Ser. A,1982,25:249-254.
[14]Feng J, Li S and Li R. An. s-strong tournament with has s + 1 vertices whose out-arcs are 4-pancyclic[J]. Discrete Applied Mathematics,2006,154:2609-2612.
[15]郭巧萍,李胜家.k-强竞赛图中外弧泛5顶点的数目[J].数学的实践与认识,2010,40：210-215.
[16]Thomassen C. Hamiltonian-connected tournaments[J]. J. Combin. Theory Ser. 1980,28:142-163.
[17]Lichiardopol N. Cycles in a tournament with pairwise zero, one or tow given vertices in common[J]. Discrete Mathematics,2008,308:763-771.
[18]Neumann-Lara V. The 3 and 4-dichromatic tournaments of minimum order[J]. Discrete Math.,1984,135:233-243
[19]Moon J W. Embedding tournaments in simple tournaments[J]. Discrete Math.,1972, 2:398-395
[20]Volkmann L. Cycles in multipartite tournaments:Results and problems[J]. Discrete Math.,2002,245:19-53.
[21]Volkmann L and Yeo A. Hamiltonian paths, containing a given path or collection of arcs, in close to regular multipartite tournaments[J]. Discrete Math.,2004,281: 267-276.
[22]Zhou G, Zhang K and Xue G. Vertex-pancyclic Multipartite Tournaments[J]. J Nanjing Univ. Natur. Ssi.,2001,37:477-485.
[23]何志红,李国君,李曙光.局部几乎正则多部竞赛图中的分量共轭圈[J].系统工程与电子技术,2009,31：2513-2515.
[24]何志红,周学勤,王晓英.局部几乎正则多部竞赛图中的外路[J].烟台大学学报,2009,22：251-254.
[25]徐高奎,李胜家.正则多部竞赛图中过任意点的强子竞赛图[J].数学的实践与认识,2010,40：232-236.
[26]Zhang K. Vertex even-pancyclic bipartite tournamonts[J]. J. Nanjing Univ. Math. Biq.,1984,1:85-88.
[27]Gutin G. Characterization of vertex pancyclic partly oriented k-partite tourna-ments[J]. Vestsi Acad. Navuk BSSR Ser. Fiz.-Mat. Navuk, 1989, 2: 41-46.
[28]Wang J. Cycles of all possible lengths in diregular bipartite tournaments[J]. Ars Combin.,1991,32:279-284.
[29]郭巧萍.强竞赛图中顶点的外弧泛圈性[D].山西大学：博士毕业论文,2010.
[2]Bondy J A and Murty U S R. Graph Theory[M]. Springer, New York, 2008.
[3]Yao T, Guo Y and Zhang K. Pancyclic out-arcs of a vertex in a tournament[J]. Discrete Appl. Math.,2000,99:245-249.
[4]Yeo A. The number of pancyclic arcs in a k-strong tournament[J]. Journal of Graph Theory, 2005,50: 212-219.
[5]Li R, Li S and Feng J. The number of vertices whose out-arcs are pancyclic in a 2-strong tournament[J]. Discrete Appl. Math.,2008,156:88-92.
[6]Feng J. Each 3-strong tournament contains 3 vertices whose out-arcs are pancyclic[J]. Graphs Combin.,2009,25:299-307.
[7]Guo Q, Li S, Guo Y and Li H. Out-arc pancyclicity of vertices in tournaments[J]. Discrete Applied Mathematics,2010,158:996-1005.
[8]Redei L. Ein kombinatorischer Satz[J]. Acta Litt. Sci. Szeged,1934,7: 39-43.
[9]Camion P. Chemins et circuits hamiltoniens des graphes complets[J]. C. R. Acad. Sci. Paris,1959,249:2151-2152.
[10]Harary F and Moser L. The theory of round robin tournaments[J]. Amer. Math. Monthly, 1966,73:231-246.
[11]Moon J W. On subtournaments of a tournament[J]. Canad. Math. Bull.,1966,9: 297-301.
[12]Alspach B. Cycles of each length in regular tournament[J]. Canad. Math. Bull., 1967,10:283-286.
[13]Wu Z, Zhang K and Zou Y. A necessary and sufficient condition for arc-pancyclicity of tournaments[J]. Sci. Sinica, Ser. A,1982,25:249-254.
[14]Feng J, Li S and Li R. An. s-strong tournament with has s + 1 vertices whose out-arcs are 4-pancyclic[J]. Discrete Applied Mathematics,2006,154:2609-2612.
[15]郭巧萍,李胜家.k-强竞赛图中外弧泛5顶点的数目[J].数学的实践与认识,2010,40：210-215.
[16]Thomassen C. Hamiltonian-connected tournaments[J]. J. Combin. Theory Ser. 1980,28:142-163.
[17]Lichiardopol N. Cycles in a tournament with pairwise zero, one or tow given vertices in common[J]. Discrete Mathematics,2008,308:763-771.
[18]Neumann-Lara V. The 3 and 4-dichromatic tournaments of minimum order[J]. Discrete Math.,1984,135:233-243
[19]Moon J W. Embedding tournaments in simple tournaments[J]. Discrete Math.,1972, 2:398-395
[20]Volkmann L. Cycles in multipartite tournaments:Results and problems[J]. Discrete Math.,2002,245:19-53.
[21]Volkmann L and Yeo A. Hamiltonian paths, containing a given path or collection of arcs, in close to regular multipartite tournaments[J]. Discrete Math.,2004,281: 267-276.
[22]Zhou G, Zhang K and Xue G. Vertex-pancyclic Multipartite Tournaments[J]. J Nanjing Univ. Natur. Ssi.,2001,37:477-485.
[23]何志红,李国君,李曙光.局部几乎正则多部竞赛图中的分量共轭圈[J].系统工程与电子技术,2009,31：2513-2515.
[24]何志红,周学勤,王晓英.局部几乎正则多部竞赛图中的外路[J].烟台大学学报,2009,22：251-254.
[25]徐高奎,李胜家.正则多部竞赛图中过任意点的强子竞赛图[J].数学的实践与认识,2010,40：232-236.
[26]Zhang K. Vertex even-pancyclic bipartite tournamonts[J]. J. Nanjing Univ. Math. Biq.,1984,1:85-88.
[27]Gutin G. Characterization of vertex pancyclic partly oriented k-partite tourna-ments[J]. Vestsi Acad. Navuk BSSR Ser. Fiz.-Mat. Navuk, 1989, 2: 41-46.
[28]Wang J. Cycles of all possible lengths in diregular bipartite tournaments[J]. Ars Combin.,1991,32:279-284.
[29]郭巧萍.强竞赛图中顶点的外弧泛圈性[D].山西大学：博士毕业论文,2010.