Petersen substitutions and the inducibility of the six-vertex tree F26
Let F = F26 be the six-vertex tree with three arms of lengths 1, 2 and 2. Its induced density tends to 480/11111 in balanced iterated substitutions of the Petersen graph. For arbitrary graphs, a rational certificate gives the upper bound 233973195106737927117969229/5415987671873538702683668480. The two bounds differ by less than 3.471 × 10⁻⁸. Among graphs containing neither an induced bull nor an induced house, the exact value is 480/11111. A graph in this class on n ≥ 1 vertices contains at most 2(n⁶ − n)/33333 induced copies of F, with equality precisely for the balanced Petersen substitutions on powers of ten vertices. In this class we also characterize equality for nonnegative vertex weights of total mass one. Both certificates can be checked offline using the accompanying data and programs.
Authors
- Oleg Kyzlasov
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24341541
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint