The number of 4-cycles and the cyclomatic number of a finite simple graph

2018/01/18 by Takayuki Hibi, Aki Mori, Hibi, Takayuki +3
Mathematics · Engineering · Computer Science · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1801.06169

Abstract

Let G be a finite connected simple graph with n vertices and m edges. We show that, when G is not bipartite, the number of 4-cycles contained in G is at most \binomm-n+12. We further provide a short combinatorial proof of the bound \binomm-n+22 which holds for bipartite graphs.

Related

• Simple cycles
• Bounding the number of cycles in a graph in terms of its degree sequence
• The Minimum Number of 4-Cycles in a Maximal Planar Graph with Small Number of Vertices
• Minimal Pancyclicity
• Upper bounds on the extremal number of the 4-cycle