The number of cycles in a Hamilton graph
Let \(f(G)\) denote the number of distinct cycles of a graph \(G\). Let \(\Gamma_ k\) be the collection of all Hamiltonian simple graphs of order \(n\) and size \(n+k\). Let \[ m(k)= \min\{f(G);\;G\in \Gamma_ k\},\quad M(k)= \max\{f(G);\;G\in \Gamma_ k\}. \] The reviewer and S. K. Teo raised the following three questions in 1982, see the reviewer and \textit{S. K. Teo} [Uniquely \(r\)-pancyclic graphs, in ``Graph theory, Singapore 1983'', Lect. Notes Math. 1073, 334-335 (1984)]: (1) Is it true that \(m(k)= (k+1)(k+2)/2\)? (2) Is it true that \(M(k)= 2^ k+ k\)? (3) For each integer \(m\in [m(k),M(k)]\), can we find a graph \(G\in \Gamma_ k\) such that \(f(G)= m\)? In this paper the author answers the first question in affirmative and the other two in negative. Moreover, the author also proves several equalities and inequalities concerning \(m(k)\) and \(M(k)\). The reviewer remarks: The three questions of the reviewer and Teo had also been answered by Chunhui Lai of Zhangzhou Teachers' College, Fujian, People's Republic of China in 1990. Lai's paper was submitted for publication to a Chinese mathematics journal.
scientific article; zbMATH DE number 681703