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 条
[31]   The maximum number of 10-and 12-cycles in a planar graph [J].
Cox, Christopher ;
Martin, Ryan R. .
DISCRETE MATHEMATICS, 2023, 346 (02)
[32]   On the maximum number of five-cycles in a triangle-free graph [J].
Grzesik, Andrzej .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (05) :1061-1066
[33]   On the Largest Graph-Lagrangian of 3-Graphs with Fixed Number of Edges [J].
Sun, Yanping ;
Tang, Qingsong ;
Zhao, Cheng ;
Peng, Yuejian .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2014, 163 (01) :57-79
[34]   On the Number of Edges in a Minimum -Saturated Graph [J].
Zhang, Mingchao ;
Luo, Song ;
Shigeno, Maiko .
GRAPHS AND COMBINATORICS, 2015, 31 (04) :1085-1106
[35]   A RANDOM GRAPH WITH A SUBCRITICAL NUMBER OF EDGES [J].
PITTEL, B .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1988, 309 (01) :51-75
[36]   The number of edges in a subgraph of a Hamming graph [J].
Squier, R ;
Torrence, B ;
Vogt, A .
APPLIED MATHEMATICS LETTERS, 2001, 14 (06) :701-705
[37]   On the Largest Graph-Lagrangian of 3-Graphs with Fixed Number of Edges [J].
Yanping Sun ;
Qingsong Tang ;
Cheng Zhao ;
Yuejian Peng .
Journal of Optimization Theory and Applications, 2014, 163 :57-79
[38]   TURANS THEOREM FOR NUMBER OF EDGES OF A GRAPH [J].
MARTINOV, N .
DOKLADI NA BOLGARSKATA AKADEMIYA NA NAUKITE, 1977, 30 (04) :479-481
[39]   ON THE NUMBER OF EDGES IN THE TRANSITIVE CLOSURE OF A GRAPH [J].
MCCOLL, WF ;
NOSHITA, K .
DISCRETE APPLIED MATHEMATICS, 1986, 15 (01) :67-73
[40]   On the number of vertices and edges of the Buneman graph [J].
A. Dress ;
M. Hendy ;
K. Huber ;
V. Moulton .
Annals of Combinatorics, 1997, 1 (1) :329-337