The maximum number of cycles in a graph with fixed number of edges

被引:0
作者
Arman, Andrii [1 ]
Tsaturian, Sergei [2 ]
机构
[1] Monash Univ, Sch Math, Melbourne, Vic, Australia
[2] Univ Manitoba, Dept Math, Winnipeg, MB, Canada
关键词
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The main problem considered in this paper is maximizing the number of cycles in a graph with given number of edges. In 2009, Kiraly 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.
引用
收藏
页数:16
相关论文
共 50 条
[21]   ON THE NUMBER OF CYCLES IN A GRAPH [J].
AlBdaiwi, Bader F. .
MATHEMATICA SLOVACA, 2018, 68 (01) :1-10
[22]   ON NUMBER OF DISJOINT EDGES IN A GRAPH [J].
WEINSTEIN, JM .
CANADIAN JOURNAL OF MATHEMATICS, 1963, 15 (01) :106-&
[23]   The maximum number of edges in a graph of bounded dimension, with applications to ring theory [J].
Agnarsson, G ;
Felsner, S ;
Trotter, WT .
DISCRETE MATHEMATICS, 1999, 201 (1-3) :5-19
[24]   THE MAXIMUM NUMBER OF EDGES IN A 3-GRAPH NOT CONTAINING A GIVEN STAR [J].
CHUNG, FRK ;
FRANKL, P .
GRAPHS AND COMBINATORICS, 1987, 3 (02) :111-126
[25]   On the maximum number of edges in a hypergraph with given matching number [J].
Frankl, Peter .
DISCRETE APPLIED MATHEMATICS, 2017, 216 :562-581
[26]   The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree [J].
Cutler, Jonathan ;
Radcliffe, A. J. .
JOURNAL OF GRAPH THEORY, 2017, 84 (02) :134-145
[27]   Minimal bricks with the maximum number of edges [J].
Feng, Xing ;
Yan, Weigen .
JOURNAL OF GRAPH THEORY, 2025, 109 (02) :152-169
[28]   MAXIMUM NUMBER OF EDGES IN CONNECTED GRAPHS WITH A GIVEN DOMINATION NUMBER [J].
SANCHIS, LA .
DISCRETE MATHEMATICS, 1991, 87 (01) :65-72
[29]   Maximum sparse induced subgraphs of the binomial random graph with given number of edges [J].
Kamaldinov, Dmitry ;
Skorkin, Arkadiy ;
Zhukovskii, Maksim .
DISCRETE MATHEMATICS, 2021, 344 (02)
[30]   MAXIMUM NUMBER OF KJ-SUBGRAPHS IN A GRAPH WITH K-INDEPENDENT EDGES [J].
DOUGLAS, RJ .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1977, 23 (2-3) :258-261