Triangle-free graphs with the maximum number of cycles

2015/01/06 by Arman, Andrii, Gunderson, David S., Tsaturian, Sergei
#05Cxx #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1501.01088

Abstract

It is shown that for n≥ 141, among all triangle-free graphs on n vertices, the complete equibipartite graph is the unique triangle-free graph with the greatest number of cycles.

Related

• Triangles in C₅-free graphs and Hypergraphs of Girth Six
• Maximising the Number of Cycles in Graphs with Forbidden Subgraphs
• Triangle-Free Equimatchable Graphs
• On the maximum number of five-cycles in a triangle-free graph
• Cycles in triangle-free graphs of large chromatic number