The number of cycles in a Hamilton graph
type: Item
instance of: scholarly article
title: The number of cycles in a Hamilton graph
zbMATH Open document ID: 0810.05049
DOI: 10.1016/0012-365X(94)90031-0
author: Yongbing Shi
published in: Discrete Mathematics
publication date: 1995-04-09T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 681703
zbMATH Keywords: number of cycles
zbMATH Keywords: Hamilton graph
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q4294627
full work available at URL: 0012-365x(94)90031-0
OpenAlex ID: W2061557180
description: scientific article; zbMATH DE number 681703