Pippinger's inducibility conjecture for cycles
Pippinger's inducibility conjecture for cycles
Let denote the cycle on vertices. For a graph , its induced density is the number of induced copies of divided by ; write for the maximum induced density of over graphs on vertices, and call the inducibility of . Pippinger's conjecture. For , the inducibility of the cycle is
This conjecture, posed by Pippinger and Golumbic in 1975, concerns the extremal induced density of fixed cycles. Apart from the case resolved in the paper, the problem remains open; see the cited work for results on the inducibility of other graphs.
Sources & referencesView supporting material
Primary source
Natasha Morrison and Alex Scott, “Maximising the number of induced cycles in a graph”, arXiv:1603.02960 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.