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 条
[41]   NUMBER OF EDGES IN A GRAPH OF A GIVEN RADIUS [J].
VIZING, VG .
DOKLADY AKADEMII NAUK SSSR, 1967, 173 (06) :1245-&
[42]   THE NUMBER OF CYCLES IN A HAMILTON GRAPH [J].
SHI, YB .
DISCRETE MATHEMATICS, 1994, 133 (1-3) :249-257
[43]   On the maximum number of colorings of a graph [J].
Erey, Aysel .
JOURNAL OF COMBINATORICS, 2018, 9 (03)
[44]   On the maximum number of cliques in a graph [J].
Wood, David R. .
GRAPHS AND COMBINATORICS, 2007, 23 (03) :337-352
[45]   On the Maximum Number of Cliques in a Graph [J].
David R. Wood .
Graphs and Combinatorics, 2007, 23 :337-352
[46]   MAXIMUM NUMBER OF TRIANGLES IN A GRAPH [J].
MARTINOV, N .
DOKLADI NA BOLGARSKATA AKADEMIYA NA NAUKITE, 1977, 30 (09) :1255-1257
[47]   On the Maximum Number of Open Triangles in Graphs with the Same Number of Vertices and Edges [J].
Pyatkin A.V. ;
Chernykh O.I. .
Journal of Applied and Industrial Mathematics, 2022, 16 (01) :116-121
[48]   On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number [J].
Jean R. S. Blair ;
Pinar Heggernes ;
Paloma T. Lima ;
Daniel Lokshtanov .
Algorithmica, 2022, 84 :3587-3602
[49]   On the maximum number of edges in planar graphs of bounded degree and matching number [J].
Jaffke, Lars ;
Lima, Paloma T. .
DISCRETE MATHEMATICS, 2023, 346 (08)
[50]   On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number [J].
Blair, Jean R. S. ;
Heggernes, Pinar ;
Lima, Paloma T. ;
Lokshtanov, Daniel .
ALGORITHMICA, 2022, 84 (12) :3587-3602