The main problem considered in this paper is maximizing the number of cycles in a graph with given number of edges. In 2009, Király 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.
@article{10_37236_8747,
author = {Andrii Arman and Sergei Tsaturian},
title = {The maximum number of cycles in a graph with fixed number of edges},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {4},
doi = {10.37236/8747},
zbl = {1428.05147},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8747/}
}
TY - JOUR
AU - Andrii Arman
AU - Sergei Tsaturian
TI - The maximum number of cycles in a graph with fixed number of edges
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/8747/
DO - 10.37236/8747
ID - 10_37236_8747
ER -
%0 Journal Article
%A Andrii Arman
%A Sergei Tsaturian
%T The maximum number of cycles in a graph with fixed number of edges
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/8747/
%R 10.37236/8747
%F 10_37236_8747
Andrii Arman; Sergei Tsaturian. The maximum number of cycles in a graph with fixed number of edges. The electronic journal of combinatorics, Tome 26 (2019) no. 4. doi: 10.37236/8747
