Let N_i be the number of connected spanning subgraphs with i(n - 1 ≤ i ≤ m) edges in an n-vertex m-edge undirected graph G = (V, E). Although N_(n-1) is computed in polynomial time by the Matrix-tree theorem, whether N_n is efficiently computed for a graph G is an open problem (see e.g., 2). On the other hand, whether N_n~2 ≥ N_(n-1)N_(n-1) for a graph G is also open as a part of log concave conjecture (see e.g., 6, 12). In this paper, for a complete graph K_n, we give the formulas for N_n, N_(n+1), by which N_n, N_(n+1) are respectively computed in polynomial time on n, and, in particular, prove N_n~2 > ((n-1)(n-2))/(n(n-3)) N_(n-1)N_(n+1) as well.
展开▼
机译：设 N_i 是 n 顶点 m 边无向图中具有 i（n - 1 ≤ i ≤ m） 边的连接跨越子图的数量 G = （V， E）。尽管 N_（n-1） 是通过矩阵树定理在多项式时间内计算的，但对于图 G 是否有效地计算N_n是一个悬而未决的问题（参见例如，[2]）。另一方面，图 G 的 N_n~2 ≥ N_（n-1）N_（n-1） 是否也作为对数凹猜想的一部分开放（参见例如 [6]、[12]）。在本文中，为了一个完整的图K_n，我们给出了N_n，N_（n+1）的公式，通过这些公式，在n上的多项式时间分别计算了N_n、N_（n+1），并证明了N_n~2>（（n-1）（n-2））/（n（n-3））N_（n-1）N_（n+1）。
展开▼
