
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.
Eulerian and Hamiltonian graphs, Hamilton graph, Discrete Mathematics and Combinatorics, number of cycles, Enumeration in graph theory, Paths and cycles, Theoretical Computer Science
Eulerian and Hamiltonian graphs, Hamilton graph, Discrete Mathematics and Combinatorics, number of cycles, Enumeration in graph theory, Paths and cycles, Theoretical Computer Science
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 13 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
