On the Number of Connected Sets in Bounded Degree Graphs

Abstract

A set of vertices in a graph is connected if it induces a connected subgraph. Using Shearer's entropy lemma and a computer search, we show that the number of connected sets in a graph with $n$ vertices and maximum vertex degree $d$ is at most $O(1.9351^n)$ for $d=3$, $O(1.9812^n)$ for $d=4$, and $O(1.9940^n)$ for $d=5$. Dually, we construct infinite families of graphs where the number of connected sets is at least $\Omega(1.7651^n)$ for $d=3$, $\Omega(1.8925^n)$ for $d=4$, and $\Omega(1.9375^n)$ for $d=5$.