Simple cycles

1999/10/19 by Igor Rivin, Rivin, Igor
Computer Science · Mathematics · #05C12 #05C35 #26D2 #Advanced Graph Theory Research #Analytic Number Theory Research #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CA #math.CO #msc:05C12 #msc:05C35 #msc:26D2

paper · pdf · doi:10.48550/arxiv.math/9910093

9 pages

arxiv created 1999/10/19 · openalex publication_date 1999/10/19 · arxiv updated 2009/11/30 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

We obtain sharp bounds for the number of n-cycles in a finite graph as a function of the number of edges, and prove that the complete graph is optimal in more ways than could be imagined. En route, we prove some sharp estimates on power sums.

Related

• Counting cycles and finite dimensional Lp norms
• Bounding the number of cycles in a graph in terms of its degree sequence
• The maximum number of cycles in a graph with fixed number of edges
• The number of 4-cycles and the cyclomatic number of a finite simple graph
• Upper bounds on the extremal number of the 4-cycle