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

Research output: Contribution to journalArticle

44 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)116-130
Number of pages15
JournalIsrael Journal of Mathematics
Volume38
Issue number1-2
DOIs
StatePublished - Mar 1 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'On the number of subgraphs of prescribed type of graphs with a given number of edges'. Together they form a unique fingerprint.

  • Cite this