标题： 正则图中连通集的最大数量 显示英文标题

标题： The maximum number of connected sets in regular graphs

摘要： 我们改进了正则图上关于连通集数量的下界，记作 $N(G)$，以及支配连通集数量的下界，记作 $N_{dom}(G)$。这些下界的改进是通过构造一族以某个小的基本图（即摩尔图）为定义基础的图实现的，利用这些图的组合约简为矩形棋盘，随后借助线性代数证明该下界与基本图相关联的系数矩阵的最大特征值有关。 此外，我们还确定了低阶立方图和四次图中 $N(G)$ 和 $N_{dom}(G)$ 的精确最大值。 我们给出了多个支持以下猜想的结果：每个摩尔图 $M$ 都能最大化基数，表明至少有 $|M|$ 个顶点且具有相同正则性的图中连通顶点子集的数量呈现指数增长行为。 我们改进了在该猜想条件下已知的关于$N(G)$和$N_{dom}(G)$的最佳上界。 显示英文摘要

摘要： 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.