MATH Seminar

Title: The maximum number of cycles in a graph
Seminar: Combinatorics
Speaker: Andrii Arman of The University of Manitoba
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2018-04-20 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: The problem of bounding the total number of cycles in a graph is more than a century old. In 1897, Ahrens proved bounds on the number of cycles using the cyclomatic number of the graph and since then many results have appeared on the maximum number of cycles in graphs with different restrictions. In this talk I will consider a problem of maximizing the number of cycles for three classes of graphs: graphs with given number of edges (and unrestricted number of vertices), graphs with a given average degree, and graphs without a clique of a specific size. For the first two classes I will show that the maximum number of cycles in a graph has bounds exponential in the number of edges of the graph. I will also present exponentially tight bounds for the maximum number of cycles in a multigraph with a fixed number of vertices and edges.