On the maximum number of cycles in a Hamiltonian graph

被引：7

作者：

Rautenbach, D

Stella, I

机构：

[1] Forsch Inst Diskrete Math, D-53113 Bonn, Germany

[2] Rhein Westfal TH Aachen, Lehrstuhl Math 2, D-52056 Aachen, Germany

来源：

DISCRETE MATHEMATICS | 2005年 / 304卷 / 1-3期

关键词：

cycle; Hamiltonian graph; number of cycles;

D O I：

10.1016/j.disc.2005.09.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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) >= 2(k) + (5/2)k(2) - (21/2)k + 14 and M(k)<= 2(k+1)-1-k (root k-2/log(2) (k)+2 - 1/4log(2)(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-2571. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：101 / 107

页数：7