TY - JOUR

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

AU - Alon, Noga

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 1981/3

Y1 - 1981/3

N2 - 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, c2 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.)

AB - 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, c2 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.)

UR - http://www.scopus.com/inward/record.url?scp=51249186590&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51249186590&partnerID=8YFLogxK

U2 - 10.1007/BF02761855

DO - 10.1007/BF02761855

M3 - Article

AN - SCOPUS:51249186590

VL - 38

SP - 116

EP - 130

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

SN - 0021-2172

IS - 1-2

ER -