On the number of connected sets in bounded degree graphs (Q1627210)

Summary: A set of vertices in a graph is \textit{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\).