完全グラフK_nにおいてn+1本以下の辺を持つ連結全域部分グラフの個数に関する計算式

摘要

Let N_i be the number of all connected spanning subgraphs with i(n-1≦i≦m) edges in an n-vertex m-edge undirected graph G=(V, E). Although N_ 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^2_n≧N_N_ for a graph G is also open as a part of log concave conjecture (see e.g., [6], [13]). In this paper, for a complete graph K_n, we give the formulas for N_n, N_, by which N_n, N_ are respectively computed in polynomial time on n, and, in particular, prove N^2_n>N_N_ as well.