Caccetta-Hggkvist猜想的注记

A Note on Caccetta-Hggkvist Conjecture

导出

摘要 1978年,Caccetta和Hggkvist提出如下至今仍未解决的猜想:最小出度不小于r的n阶有向图含有长度不大于[n/r]的有向圈.本文证明了:当α≥0.28724时,最小出度至少αn的n阶有向图含有长度不超过4的有向圈. In 1978, Caccetta and Haggkvist made an open conjecture： Any digraph on n vertices with minimum outdegree at least r contains a directed cycle of length at most [n/r]. We prove that if a ≥ 0.28724, then any digraph on n vertices with minimum outdegree at least an contains a directed cycle of length at most 4.

作者梁浩徐俊明

机构地区西南财经大学经济数学学院中国科学技术大学数学科学学院中国科学院吴文俊重点实验室

出处《数学学报（中文版）》 SCIE CSCD 北大核心 2013年第4期479-486,共8页 Acta Mathematica Sinica：Chinese Series

基金国家自然科学基金资助项目(11071233)

关键词有向图有向圈 Caccetta-Haggkvist猜想 digraph directed cycle Caccetta-Haiggkvist conjecture

分类号 O157.5 [理学—基础数学]

引文网络
相关文献

参考文献12

1Bondy J. A., Counting subgraphs: A new approach to the Caccetta-Hggkvist conjecture, Discrete Math., 1997, 165/166: 71-80.
2Caccetta L., Hggkvist R., On minimal digraphs with given girth, Proc. 9th S-E Conf. Combinatorics, Graph Theory and Computing, 1978: 181-187.
3Hamburger P., Haxell P., Kostochka A., On the directed triangles in digraphs, Electronic J. Combin., 2007, 14: Note 19.
4Hamidoune Y. O., A note on minimal directed graphs with given girth, J. Combin. Theory, Set. B, 1987, 43(3): 343-348.
5Hong C., Reed B, A note on short cycles in digraphs, Discrete Math., 1987, 66(1-2): 103-107.
6Hladky J., Kr1' D., Norin S., Counting flags in triangle-free digraphs, Electron. Notes Discrete Math., 2009, 34: 621-625. .
7Li Q., Brualdi R. A., On minimal regular digraphs with girth 4, Czechoslovak Math. J., 1983, 33: 439-447.
8Shen J., Directed triangles in digraphs, J. Combin. Theory, Set. B, 1998, 74:405-407.
9Shen J., On the girth of digraphs, Discrete Math., 2000, 211(1-3):167-181.
10Sullivan B., A summary of results and problems related to the Caccetta-Higgkvist conjecture, Arxiv preprint math/0605646, 2006-arxiv.org.

1梁浩,徐俊明.有向图最小圈长不大于4的一个充分条件[J].吉林大学学报（理学版）,2013,51(2):241-243.
2徐根玖,苏军,张胜贵.有向图的结合数与计算[J].工程数学学报,2007,24(3):527-534.
3郭巧萍,李胜家.强竞赛图中的外弧4泛顶点[J].中北大学学报（自然科学版）,2013,34(6):606-609.
4徐光辉,管宇.有向图的谱半径的一个Sharp上界[J].江西师范大学学报（自然科学版）,2004,28(2):159-162.

数学学报（中文版）

2013年第4期

浏览历史

内容加载中请稍等...

Caccetta-Hggkvist猜想的注记

参考文献12

相关作者

相关机构

相关主题

浏览历史