On the number of certain subgraphs contained in graphs with a given number of edges |
| |
Authors: | Noga Alon |
| |
Institution: | (1) School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, Israel |
| |
Abstract: | All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphsG, H, letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also, forl≧0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We determineN(l, H) precisely for alll≧0 whenH is a disjoint union of two stars, and also whenH is a disjoint union ofr≧3 stars, each of sizes ors+1, wheres≧r. We also determineN(l, H) for sufficiently largel whenH is a disjoint union ofr stars, of sizess
1≧s
2≧…≧s
r>r, provided (s
1−s
r)2<s
1+s
r−2r. We further show that ifH is a graph withk edges, then the ratioN(l, H)/l
k tends to a finite limit asl→∞. This limit is non-zero iffH is a disjoint union of stars. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|