On the number of connected sets with the neighborhood of a given size in a graph ?
We obtain upper bounds of the form 2g(1??) for the number of d-connected sets in a graph with the neighborhood of a given size. These bounds allow us to obtain asymptotic results for some classes of enumeration problems.
neighborhood asymptotics enumeration subgraph