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
Version:
Accepted Manuscript

### Access Document

Files:
• (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
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
Pubs id:
pubs:938278
URN:
uri:cb5ac3bb-8f81-4ab2-ae47-5614ffe71b75
UUID:
uuid:cb5ac3bb-8f81-4ab2-ae47-5614ffe71b75
Local pid:
pubs:938278
Keywords:

### Metrics

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP