### Abstract

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For a graph H=〈V(H), E(H)〉 and for S ⊂V(H) define N(S)={x ∈V(H):xy ∈E(H) for some y ∈S}. Define also δ(H)= max {|S| - |N(S)|:S ⊂V(H)}, γ(H)=1/2(|V(H)|+δ(H)). 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 investigate the asymptotic behaviour of N(l, H) for fixed H as l tends to infinity. The main results are:Theorem A. For every graph H there are positive constants c_{ 1}, c_{2} such that {fx116-1}. Theorem B. If δ(H)=0 then {fx116-2}, where |Aut H|is the number of automorphisms of H. (It turns out that δ(H)=0 iff H has a spanning subgraph which is a disjoint union of cycles and isolated edges.)

Original language | English (US) |
---|---|

Pages (from-to) | 116-130 |

Number of pages | 15 |

Journal | Israel Journal of Mathematics |

Volume | 38 |

Issue number | 1-2 |

DOIs | |

State | Published - Mar 1 1981 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)