On the maximum number of cycles in a Hamiltonian graph (Q2576841): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/j.disc.2005.09.007 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1968656937 / rank | |||
Normal rank | |||
Revision as of 23:55, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the maximum number of cycles in a Hamiltonian graph |
scientific article |
Statements
On the maximum number of cycles in a Hamiltonian graph (English)
0 references
29 December 2005
0 references
Let \(M(k)\) denote the maximum number of cycles in a Hamiltonian graph of order \(n\) and size \(n+k.\) \textit{Y. Shi} [Discrete Math. 133, 249--257 (1994; Zbl 0810.05049)] proved that \(2^{k}+k(k-1)+1\leq M(k)\leq 2^{k+1}-1.\) In the present paper the values of \(M(k)\) for \(5\leq k\leq 10\) are determined and an improvment in the error term of Shi's bound is given.
0 references
