On The Number Of Sets Of Cycle Lengths
On The Number Of Sets Of Cycle Lengths
复制标题
关于周期长度的组数
DOI：
10.1007/s00493-004-0043-6
复制
发表时间：
2004
期刊：
影响因子：
1.1
通讯作者：
Jacques Verstraëte
中科院分区：
文献类型：
--
作者：
Jacques Verstraëte
一个整数集合S称为{1，2，. . ., n}，如果存在一个n阶图G，使得G中的圈长集为S. Erdeggs指出，{1，2，. . ., n}是o（2n）。本文通过证明存在一个绝对常数c ≥ 0.1使得{1，2，. . ., n =$$
o{\left（{2^{{n - n^{c} \right）}
$$.
A set S of integers is called a cycle set on {1, 2, . . .,n} if there exists a graph G on n vertices such that the set of lengths of cycles in G is S. Erdős conjectured that the number of cycle sets on {1, 2, . . .,n} is o(2n). In this paper, we verify this conjecture by proving that there exists an absolute constant c ≥ 0.1 such that the number of cycle sets on {1, 2, . . .,n} is $$
o{\left( {2^{{n - n^{c} }} } \right)}
$$.