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.
@article{10_37236_12625,
author = {Stijn Cambie and Jorik Jooken and Jan Goedgebeur},
title = {The maximum number of connected sets in regular graphs},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/12625},
zbl = {1559.05078},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12625/}
}
TY - JOUR
AU - Stijn Cambie
AU - Jorik Jooken
AU - Jan Goedgebeur
TI - The maximum number of connected sets in regular graphs
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/12625/
DO - 10.37236/12625
ID - 10_37236_12625
ER -
%0 Journal Article
%A Stijn Cambie
%A Jorik Jooken
%A Jan Goedgebeur
%T The maximum number of connected sets in regular graphs
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/12625/
%R 10.37236/12625
%F 10_37236_12625
Stijn Cambie; Jorik Jooken; Jan Goedgebeur. The maximum number of connected sets in regular graphs. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/12625
