Triangle-free graphs with the maximum number of cycles

DOI10.1016/J.DISC.2015.10.008zbMATH Open1327.05170arXiv1501.01088OpenAlexW2109408352MaRDI QIDQ898130FDOQ898130

Authors: Andrii Arman, Sergei Tsaturian, David S. Gunderson 

Publication date: 8 December 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1501.01088

Recommendations

• Cycle-maximal triangle-free graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• On the Maximum Number of Triangles in Wheel-Free Graphs
• scientific article; zbMATH DE number 970792
• Pentagons in triangle-free graphs

zbMATH Keywords

triangle-freeHamiltonian cyclescycle-maximalmaximum number of cycles

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Bessel and Airy functions, cylinder functions, ({}_0F_1) (33C10)

Cites Work

• Title not available (Why is that?)
• On the number of cycles in 3-connected cubic graphs
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• A Remark on Stirling's Formula
• Title not available (Why is that?)
• On the Number of Cycles in Planar Graphs
• Title not available (Why is that?)
• On the maximum number of cycles in a planar graph
• On the maximum number of cycles in a Hamiltonian graph
• Title not available (Why is that?)
• The number of cycles in a Hamilton graph
• Estimations for the number of cycles in a graph
• Bounding the locality of distributed routing algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cycle-maximal triangle-free graphs
• Title not available (Why is that?)
• Graphentheoretische Extremalprobleme
• On the maximum number of cycles in outerplanar and series-parallel graphs
• Title not available (Why is that?)
• Extremal numbers for odd cycles
• Cycles in the complement of a tree or other graph
• The maximum number of cycles in the complement of a tree
• Cycles in the complement of a tree
• Graphs with large maximum degree containing no odd cycles of a given length
• Title not available (Why is that?)
• On the number of longest and almost longest cycles in cubic graphs.
• On the Number of Simple Cycles in Planar Graphs
• Asymptotic behavior of Golomb's Z(n) conjecture (Corresp.)

Cited In (12)

• Maximising the number of cycles in graphs with forbidden subgraphs
• The maximum number of cycles in a graph with fixed number of edges
• Maximising the number of induced cycles in a graph
• Title not available (Why is that?)
• The maximum number of induced open triangles in graphs of a given order
• Further notes on: Largest triangle-free subgraphs in powers of cycles
• The number of 4-cycles in triangle-free oriented graphs
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• Title not available (Why is that?)
• Cycle-maximal triangle-free graphs
• On maximal triangle‐free graphs
• Triangle-free subgraphs of powers of cycles

This page was built for publication: Triangle-free graphs with the maximum number of cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898130)