On the number of subgraphs of prescribed type of graphs with a given number of edges

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 ₁, c₂ 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.)