Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646668 | Discrete Mathematics | 2016 | 13 Pages |
Abstract
It is shown that for n≥141n≥141, among all triangle-free graphs on nn vertices, the balanced complete bipartite graph K⌈n/2⌉,⌊n/2⌋K⌈n/2⌉,⌊n/2⌋ is the unique triangle-free graph with the maximum number of cycles. Using modified Bessel functions, tight estimates are given for the number of cycles in K⌈n/2⌉,⌊n/2⌋K⌈n/2⌉,⌊n/2⌋. Also, an upper bound for the number of Hamiltonian cycles in a triangle-free graph is given.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Andrii Arman, David S. Gunderson, Sergei Tsaturian,