The maximum number of cycles in a graph with fixed number of edges (Q2278119): Difference between revisions

Summary: The main problem considered in this paper is maximizing the number of cycles in a graph with given number of edges. \textit{Z. Király} [Maximum number of cycles and Hamiltonian cycles in sparse graphs. EGRES Techn. Rep. No. 2009--03, \url{https://web.cs.elte.hu/egres/tr/egres-09-03.pdf}] conjectured that there is constant \(c\) such that any graph with \(m\) edges has at most \(c(1.4)^m\) cycles. In this paper, it is shown that for sufficiently large \(m\), a graph with \(m\) edges has at most \((1.443)^m\) cycles. For sufficiently large \(m\), examples of a graph with \(m\) edges and \((1.37)^m\) cycles are presented. For a graph with given number of vertices and edges an upper bound on the maximal number of cycles is given. Also, bounds tight up to a constant are presented for the maximum number of cycles in a multigraph with given number of edges, as well as in a multigraph with given number of vertices and edges.