Papers › The maximum number of connected sets in regular graphs
The maximum number of connected sets in regular graphs
Stijn Cambie, Jan Goedgebeur, Jorik Jooken
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We improve the best known lower bounds on the exponential behavior of the maximum of the number of connected sets, N(G), and dominating connected sets, N_(dom)(G), for regular graphs. These lower bounds are improved by constructing a family of graphs defined in terms of a small base graph (a Moore graph), using a combinatorial reduction of these graphs to rectangular boards followed by using linear algebra to show that the lower bound is related to the largest eigenvalue of a coefficient matrix associated with the base graph. We also determine the exact maxima of N(G) and N_(dom)(G) for cubic and quartic graphs of small order. We give multiple results in favor of a conjecture that each Moore graph M maximizes the base indicating the exponential behavior of the number of connected vertex subsets among graphs with at least |M| vertices and the same regularity. We improve the best known upper bounds for N(G) and N_(dom)(G) conditional on this conjecture.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections