On the number of certain subgraphs contained in graphs with a given number of edges
type: Item
instance of: scholarly article
title: On the number of certain subgraphs contained in graphs with a given number of edges
zbMATH Open document ID: 0588.05038
DOI: 10.1007/BF02772673
published in: Israel Journal of Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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.
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3943861
author: Noga Alon
MaRDI profile type: Publication
cites work: On the number of subgraphs of prescribed type of graphs with a given number of edges
cites work: Q5724802
description: scientific article; zbMATH DE number 3943861