The number of 4-cycles in a graph

作者：Li, Ting; Ren, Han^*

来源：APPLIED MATHEMATICS AND COMPUTATION, 2022, 428: 127211.

DOI：10.1016/j.amc.2022.127211

• Turan number
• Erdos conjecture
• 4-cycles

In extremal graph theory studies, it is not yet finished to determine the exact value of ex(n; C-4) in general case. Erdos and Simonovits [10] conjectured that an n-vertex graph G with ex(n; C-4 ) + 1 edges may contain at least root n + o(root n) 4-cycles. In this paper we investigate the number of 4-cycles in a graph. We show that the number of 4-cycles in an n-vertex graph G is at least (epsilon root 4n - 3 )/4 + epsilon(2)/(2n) provided that |E(G)| = n (1 + root 4n - 3 )/4 + epsilon, where epsilon is an arbitrary positive real number. This result is an approach solving to this open problem. Furthermore, we prove that if n is large enough, then there are at least ((4 epsilon - 1)root 4n - 3 + 5)/16 + o(1) 4-cycles in an n-vertex graph with e = (n - 1)(1 + root 4n - 3 )/4 + epsilon edges which has k vertices whose degrees are mutually different, where k >= 3 root 24n +3 root 12n -(12n)(2) - 1/27 and epsilon > 0 is a real number. In addition, we get that a triangle-free graph with n vertices and e = n root n - 1/2 + epsilon edges has at least (2 epsilon(root n - 1 - 2) + 1)/4 + o(1) 4-cycles, where epsilon > 0 is an any real number and n is large enough. This shows that the weak version of Erdos and Simonovits' conjecture [10] holds for such graphs when n is sufficiently large. Finally, we obtain a bipartite version of this result.