Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9513012 | Discrete Mathematics | 2005 | 7 Pages |
Abstract
Let M(k) denote the maximum number of cycles in a Hamiltonian graph of order n and size n+k. We prove that M(k)⩾2k+(5/2)k2-(21/2)k+14 and M(k)⩽2k+1-1-kk-2log2(k)+2-14log2(k) for k⩾4. Furthermore, we determine M(k) and the structure of the extremal graphs for 5⩽k⩽10 exactly. Our results give partial answers to a problem raised by Shi [The number of cycles in a hamilton graph, Discrete Math. 133 (1994) 249-257].
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dieter Rautenbach, Irene Stella,