Triangle-free graphs with the maximum number of cycles

DOI10.1016/J.DISC.2015.10.008MaRDI QIDQ898130zbMATH OpenOpenAlexFDO

Authors Andrii Arman, Sergei Tsaturian, David S. Gunderson

Publication date 8 December 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cycle-maximalHamiltonian cyclesmaximum number of cyclestriangle-free

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(12)

• Triangle-free subgraphs of powers of cycles
• The number of 4-cycles in triangle-free oriented graphs
• The maximum number of induced open triangles in graphs of a given order
• 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
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• Further notes on: Largest triangle-free subgraphs in powers of cycles
• On maximal triangle‐free graphs
• scientific article; zbMATH DE number 1047729 (Why is no real title available?)
• Cycle-maximal triangle-free graphs
• scientific article; zbMATH DE number 7297127 (Why is no real title available?)

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)