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

### Access Document

Files:
• (Accepted manuscript, pdf, 256.3KB)
Publisher copy:
10.1016/j.endm.2017.07.012

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS Division
Department:
Mathematical Institute
Department:
Unknown
Role:
Author
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
Keywords:
Pubs id:
pubs:938278
UUID:
uuid:cb5ac3bb-8f81-4ab2-ae47-5614ffe71b75
Local pid:
pubs:938278
Deposit date:
2018-11-09