Triangle-free graphs with the maximum number of cycles
| Autor: | David S. Gunderson, Sergei Tsaturian, Andrii Arman |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
010102 general mathematics 0102 computer and information sciences Computer Science::Computational Geometry 01 natural sciences Complete bipartite graph Upper and lower bounds Graph Theoretical Computer Science Combinatorics symbols.namesake 010201 computation theory & mathematics FOS: Mathematics symbols Bipartite graph Mathematics - Combinatorics Discrete Mathematics and Combinatorics Cycle basis Combinatorics (math.CO) Graph toughness 0101 mathematics 05Cxx Pancyclic graph Bessel function Mathematics |
| Zdroj: | Discrete Mathematics. 339:699-711 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2015.10.008 |
| Popis: | It is shown that for n ? 141 , among all triangle-free graphs on n vertices, the balanced complete bipartite graph 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 ? . Also, an upper bound for the number of Hamiltonian cycles in a triangle-free graph is given. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect