On the inducibility of cycles
| Autor: | Dan Hefetz, Mykhaylo Tyomkyn |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Conjecture
Applied Mathematics 010102 general mathematics Multiplicative function 0102 computer and information sciences 01 natural sciences Upper and lower bounds Graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics 0101 mathematics Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics |
| DOI: | 10.1016/j.jctb.2018.04.008 |
| Popis: | In 1975 Pippenger and Golumbic proved that any graph on n vertices admits at most 2 e ( n / k ) k induced k-cycles. This bound is larger by a multiplicative factor of 2e than the simple lower bound obtained by a blow-up construction. Pippenger and Golumbic conjectured that the latter lower bound is essentially tight. In the present paper we establish a better upper bound of ( 128 e / 81 ) ⋅ ( n / k ) k . This constitutes the first progress towards proving the aforementioned conjecture since it was posed. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|