The Maximum Number of Connected Sets in Regular Graphs

Abstract

We make some fundamental observations and conjectures on the number of connected sets $N(G)$ in $d$-regular graphs $G$. We improve the best known lower bounds on the exponential behavior of the maximum of $N(G)$ for regular graphs by considering a different construction of a family of graphs (depending on smaller base graphs) and improve the upper bounds conditional on one of our conjectures. The lower bounds are estimated using combinatorial reductions and linear algebra. We also determine the exact maxima of $N(G)$ for cubic and quartic graphs with small order.