The number of cycles in a Hamilton graph (Q1336706)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The number of cycles in a Hamilton graph |
scientific article |
Statements
The number of cycles in a Hamilton graph (English)
0 references
9 April 1995
0 references
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.
0 references
number of cycles
0 references
Hamilton graph
0 references