All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphs G, H, let N(G, H) denote the number of subgraphs of G isomorphic to H. Define also, for l≧0, N(l, H)=max N(G, H), where the maximum is taken over all graphs G with l edges. We determine N(l, H) precisely for all l≧0 when H is a disjoint union of two stars, and also when H is a disjoint union of r≧3 stars, each of size s or s+1, where s≧r. We also determine N(l, H) for sufficiently large l when H is a disjoint union of r stars, of sizes s 1≧s 2≧...≧s r>r, provided (s 1-s r)2<s 1+s r-2 r. We further show that if H is a graph with k edges, then the ratio N(l, H)/l k tends to a finite limit as l→∞. This limit is non-zero iff H is a disjoint union of stars.
|Original language||English (US)|
|Number of pages||24|
|Journal||Israel Journal of Mathematics|
|State||Published - Feb 1986|
All Science Journal Classification (ASJC) codes