Journal article icon

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

Actions


Access Document


Files:
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

Terms of use


Metrics



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

TO TOP