On the number of certain subgraphs contained in graphs with a given number of edges (Q1073050): Difference between revisions

If G, H are two graphs then N(G,H) denotes the number of subgraphs of G isomorphic to H. By N(\(\ell,H)\) the author means the maximum value of N(G,H) taken over all graphs G with \(\ell\) edges. In his preceding paper [ibid. 38, 116-130 (1981; Zbl 0472.05034)] he investigated the asymptotic behaviour of N(\(\ell,H)\) for fixed H as \(\ell \to \infty\). In the paper under review he finds formulas for N(\(\ell,H)\) when H is a disjoint union of two stars and also when H is a disjoint union of \(r\geq 3\) stars, each of size s or \(s+1\), where \(s\geq r\). The author also succeeded in determining the value N(\(\ell,H)\) for sufficiently large \(\ell\) when H is a disjoint union of r stars of sizes \(s_ 1\geq s_ 2\geq...\geq s_ r>r\), provided \((s_ 1-s_ r)^ 2<s_ 1+s_ r-2r\). Finally it turns out that if H has k edges, then the ratio \(N(\ell,H)/\ell^ k\) tends to a finite limit as \(\ell \to \infty\). The limit is non-zero if and only if H is a disjoint union of stars.