有向图最小圈长不大于4的一个充分条件

J4 ›› 2013, Vol. 51 ›› Issue (02): 241-243.

有向图最小圈长不大于4的一个充分条件

梁浩^1, 徐俊明²

1. 西南财经大学经济数学学院, 成都 611130； 2. 中国科学技术大学数学科学学院, 合肥 230026

收稿日期:2012-06-06 出版日期:2013-03-26 发布日期:2013-03-27
通讯作者: 梁浩 E-mail:lianghao@mail.ustc.edu.cn

A Sufficient Condition for Digraphs with Girth at Most 4

LIANG Hao¹, XU Junming²

1. College of Mathematics, Southwestern University of Finance and Economics, Chengdu 611130, China;2. School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

Received:2012-06-06 Online:2013-03-26 Published:2013-03-27
Contact: LIANG Hao E-mail:lianghao@mail.ustc.edu.cn

摘要/Abstract

摘要：

运用组合计数的方法, 给出了与CaccettaHaggkvist猜想有关的一个近似结果, 即给出最小出度至少为αn的n阶有向图含有长度不超过4的有向圈的充分条件： α≥0.288 66.

关键词: 有向图, 有向圈, 出度, 定向三角形, 充分条件

Abstract:

Using some combinatorial techniques, the authors gave an approximate result related to CaccettaHaggkvist conjecture, that is, a sufficient condition α≥0.288 66 for which any digraph on n vertices with minimum outdegree at least αn contains a directed cycle of length at most 4.

Key words: digraph, directed cycle, outdegree, transitive triangle, sufficient condition

中图分类号:

O157.5

梁浩, 徐俊明. 有向图最小圈长不大于4的一个充分条件[J]. J4, 2013, 51(02): 241-243.

LIANG Gao, XU Dun-Meng. A Sufficient Condition for Digraphs with Girth at Most 4[J]. J4, 2013, 51(02): 241-243.

[1]	汪荣, 邵燕灵, 高玉斌. 一类双色有向图本原指数的上界[J]. J4, 2008, 46(04): 601-606.
[2]	赫枫龄, 左万利. 用有向图法解决网页爬行中循环链接问题[J]. J4, 2004, 42(03): 402-404.
[3]	李忠范，王彩玲，刘停战. 一类Dini广义凸非光滑多目标规划的充分条件[J]. J4, 2004, 42(01): 50-53.