The maximum number of connected sets in regular graphs
| Autor: | Cambie, Stijn, Goedgebeur, Jan, Jooken, Jorik |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 19 Pages, 8 figures, 5 tables |
| Databáze: | arXiv |
| Externí odkaz: |
|