A new lower bound for the inducibility of a graph. (English) Zbl 0612.05038

Let G be a p-vertex graph. For an arbitrary n-vertex graph H (n\(\geq p)\), let \({\mathcal I}(G,H)\) denote the number of induced subgraphs of H that are isomorphic to G. Let I(G,n) denote the maximum of \({\mathcal I}(G,H)/\left( \begin{matrix} n\\ p\end{matrix} \right)\) taken over all n-vertex graphs H. M. C. Pippenger and the reviewer [J. Comb. Theory, Ser. B 19, 189-203 (1975; Zbl 0332.05119)] have shown that the sequence I(G,n) is nonincreasing and have defined the inducibility of G to be the limit \(I(G)=\lim_{n\to \infty}I(G,n)\). They proved a lower bound for the inducibility given by I(G)\(\geq p!(p^ p-p)^{-1}.\)
In the paper under review the author gives a more general formula for the lower bound of I(G) which includes the previous bound as a special case and is an improvement upon previous bounds for an infinite family of graphs.


05C35 Extremal problems in graph theory


Zbl 0332.05119
Full Text: EuDML


[1] BERGE, C: Graphs and Hypergraphs. North Holland, Amsterdam-London, 1973, 396-397.
[2] HARARY F.: Graph Theory. Addison-Wesley, Reading, Mass., 1969. · Zbl 0182.57702
[3] PIPPENGER N., GOLUMBIC M. CH.: The Inducibility of a Graph. J. Comb. Theory (B)19, 1975, 189-203. · Zbl 0332.05119
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.