论文标题
关于森林和连接的子图的数量
On the number of forests and connected spanning subgraphs
论文作者
论文摘要
令$ f（g）$为图$ g $的森林数量。同样，让$ c（g）$是连接图形$ g $的连接子图的数量。我们绑定了常规图的$ f（g）$和$ c（g）$，以及固定平均度的图形。在许多其他方面，我们研究$ f_d = \ sup_ {g \ in \ mathcal {g} _d} f（g）^{1/v（g）} $，其中$ \ nathcal {g} _d $是$ d $的家族，$ d $ - 常规图形和$ v（g）$ demotes $ demotes $ demte n $ vertes $ vert $ g $ g $ g $ g $ g $ g $。 We show that $f_3=2^{3/2}$, and if $(G_n)_n$ is a sequence of $3$--regular graphs with length of the shortest cycle tending to infinity, then $\lim_{n\to \infty}F(G_n)^{1/v(G_n)}=2^{3/2}$.我们还以$ 4 \ leq d \ leq 9 $为$ f_d $的先前最佳界限。
Let $F(G)$ be the number of forests of a graph $G$. Similarly let $C(G)$ be the number of connected spanning subgraphs of a connected graph $G$. We bound $F(G)$ and $C(G)$ for regular graphs and for graphs with fixed average degree. Among many other things we study $f_d=\sup_{G\in \mathcal{G}_d}F(G)^{1/v(G)}$, where $\mathcal{G}_d$ is the family of $d$--regular graphs, and $v(G)$ denotes the number of vertices of a graph $G$. We show that $f_3=2^{3/2}$, and if $(G_n)_n$ is a sequence of $3$--regular graphs with length of the shortest cycle tending to infinity, then $\lim_{n\to \infty}F(G_n)^{1/v(G_n)}=2^{3/2}$. We also improve on the previous best bounds on $f_d$ for $4\leq d\leq 9$.
