Premium
Cycles of even lengths modulo k
Author(s) -
Diwan Ajit A.
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20477
Subject(s) - modulo , mathematics , combinatorics , conjecture , graph , discrete mathematics
Thomassen [J Graph Theory 7 (1983), 261–271] conjectured that for all positive integers k and m , every graph of minimum degree at least k +1 contains a cycle of length congruent to 2 m modulo k . We prove that this is true for k ⩾2 if the minimum degree is at least 2 k −1, which improves the previously known bound of 3 k −2. We also show that Thomassen's conjecture is true for m = 2. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 246–252, 2010