Journal article
On the inducibility of cycles
- Abstract:
- In 1975 Pippenger and Golumbic proved that any graph on n vertices admits at most 2e(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 (128e/81)⋅(n/k)k. This constitutes the first progress towards proving the aforementioned conjecture since it was posed.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Accepted manuscript, pdf, 256.3KB)
-
- Publisher copy:
- 10.1016/j.endm.2017.07.012
Authors
Funding
Bibliographic Details
- Publisher:
- Elsevier Publisher's website
- Journal:
- Electronic Notes in Discrete Mathematics Journal website
- Volume:
- 61
- Pages:
- 593-599
- Publication date:
- 2017-08-03
- DOI:
- ISSN:
-
1571-0653
- Source identifiers:
-
938278
Item Description
- Keywords:
- Pubs id:
-
pubs:938278
- UUID:
-
uuid:cb5ac3bb-8f81-4ab2-ae47-5614ffe71b75
- Local pid:
- pubs:938278
- Deposit date:
- 2018-11-09
Terms of use
- Copyright holder:
- Elsevier BV
- Copyright date:
- 2017
- Notes:
- Copyright © 2017 Elsevier B.V. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: https://doi.org/10.1016/j.endm.2017.07.012
If you are the owner of this record, you can report an update to it here: Report update to this record