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] The Size of a Maximum Subgraph of the Random Graph with a Given Number of Edges
    Derevyanko, N. M.
    Zhukovskii, M. E.
    Rassias, M.
    Skorkin, A. Yu.
    DOKLADY MATHEMATICS, 2019, 100 (02) : 478 - 479
  • [22] ON THE NUMBER OF CYCLES IN A GRAPH
    AlBdaiwi, Bader F.
    MATHEMATICA SLOVACA, 2018, 68 (01) : 1 - 10
  • [23] ON NUMBER OF DISJOINT EDGES IN A GRAPH
    WEINSTEIN, JM
    CANADIAN JOURNAL OF MATHEMATICS, 1963, 15 (01): : 106 - &
  • [24] The maximum number of edges in a graph of bounded dimension, with applications to ring theory
    Agnarsson, G
    Felsner, S
    Trotter, WT
    DISCRETE MATHEMATICS, 1999, 201 (1-3) : 5 - 19
  • [25] THE MAXIMUM NUMBER OF EDGES IN A 3-GRAPH NOT CONTAINING A GIVEN STAR
    CHUNG, FRK
    FRANKL, P
    GRAPHS AND COMBINATORICS, 1987, 3 (02) : 111 - 126
  • [26] On the maximum number of edges in a hypergraph with given matching number
    Frankl, Peter
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 562 - 581
  • [27] The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
    Cutler, Jonathan
    Radcliffe, A. J.
    JOURNAL OF GRAPH THEORY, 2017, 84 (02) : 134 - 145
  • [28] Maximum sparse induced subgraphs of the binomial random graph with given number of edges
    Kamaldinov, Dmitry
    Skorkin, Arkadiy
    Zhukovskii, Maksim
    DISCRETE MATHEMATICS, 2021, 344 (02)
  • [29] Minimal bricks with the maximum number of edges
    Feng, Xing
    Yan, Weigen
    JOURNAL OF GRAPH THEORY, 2023, : 152 - 169
  • [30] Minimal bricks with the maximum number of edges
    Feng, Xing
    Yan, Weigen
    Journal of Graph Theory, 2025, 109 (02) : 152 - 169