一类HAMILTON图中圈的数目

THE NUMBER OF CYCLES IN SOME HAMILTONIAN GRAPHS

Yap H P和Teo S K提出问题:下述等式是否成立?m(K)=(1/2)(k+1)×(k+2),M(k)=2~k+k。此外,对于任意介于m(k)与M(k)之间的整数i,是否存在G∈H(n,k)使得f(G,k)=i?本文解决了上述问题。

Let H(n , k) = {G |G is a Hamiltonian graph , | V(G )l = n , |E(G )| - n + k}. If G ∈H (n , k) , let f(G , k) be the nunber of distinct cycles of G , in (k)=min {k(G , k)|G∈H(n , k)}and M(k)=max{f(G ,k)| G∈H(n ,k)}. The following results are proved: If k≤n-3, then m U)=(1/2)(k+l)(k+2); If n-3<k≤(l/2)n (n-3), then m (A:) >( l/2)(k+1 )(k+2) . If k≤(l/2) ×(n-2) , then M(k)≥2k+(l/2)k (k+ 1) . M (k) ≤2k+1- 1 - If A≥4, there is no G∈H (n , k) , such that f(G , k) = ( 1/2)(k+ 1 )(k+2) + 1 .