## Abstract

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) |
---|---|

Pages (from-to) | 97-120 |

Number of pages | 24 |

Journal | Israel Journal of Mathematics |

Volume | 53 |

Issue number | 1 |

DOIs | |

State | Published - Feb 1986 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)