Ramsey Results for Cycle Spectra
Ramsey Results for Cycle Spectra
复制标题
拉姆齐循环光谱结果
DOI：
10.1002/jgt.21704
复制
发表时间：
2013
影响因子：
0.9
通讯作者：
D. Rautenbach
中科院分区：
文献类型：
--
作者：
S. Brandt;Felix Joos;Janina Müttel;D. Rautenbach
设C（G）表示n阶图G的圈长集，G <$表示G的补图.证明了当n≥6时，C（G）<$C（G <$）包含所有3≤ k ≤co的奇整数和所有4≤ k ≤ce的偶整数，其中co和ce分别表示C（G）<$C（G <$）中的最大奇整数和最大偶整数.由此我们推出集合C（G）<$C（G <$）至少包含2n 3 −2个整数，这是尖锐的。
Let C(G) denote the set of lengths of cycles of a graph G of order n and let G¯ denote the complement of G. We show that if n≥6 , then C(G)∪C(G¯) contains all odd ℓ with 3≤ℓ≤co and all even ℓ with 4≤ℓ≤ce , where co and ce denote the maximum odd and the maximum even integer in C(G)∪C(G¯) , respectively. From this we deduce that the set C(G)∪C(G¯) contains at least 2n3−2 integers, which is sharp.