DISJOINT CHORDED CYCLES OF THE SAME LENGTH

作者：Chen Guantao^*; Gould Ronald J; Hirohata Kazuhide; Ota Katsuhiro; Shan Songling

来源：SIAM Journal on Discrete Mathematics, 2015, 29(2): 1030-1041.

DOI：10.1137/130929837

• minimum degree
• cycles
• chorded cycles

Bollobas and Thomason showed that a multigraph of order n and size at least n + c (c >= 1) contains a cycle of length at most 2(left perpendicularn/cright perpendicular + 1)left perpendicularlog(2) 2cright perpendicular. We show in this paper that a multigraph (with no loop) of order n and minimum degree at least 5 contains a chorded cycle (a cycle with a chord) of length at most 300 log(2) n. As an application of this result, we show that a graph of sufficiently large order with minimum degree at least 3k + 8 contains k vertex-disjoint chorded cycles of the same length, which is analogous to Verstraete's result: A graph of sufficiently large order with minimum degree at least 2k contains k vertex-disjoint cycles of the same length.

• 出版日期2015