On the number of certain subgraphs contained in graphs with a given number of edges

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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 languageEnglish (US)
Pages (from-to)97-120
Number of pages24
JournalIsrael Journal of Mathematics
Volume53
Issue number1
DOIs
StatePublished - Feb 1986

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

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

Cite this