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

概要

論文の詳細を見る
Let N_i (G) denote the number of connected spanning i-edge subgraphs in an n-vertex m-edge undirected graph G=(V,E). Although N_<n-1> (G) is computed in polynomial time by the Matrix-Tree theorem, whether N_n (G) is efficiently computed for a graph G is an unsolved problem. On the other hand, whether N_n (G)^2≧ N_<n-1> (G) N_<n+1> (G) for a graph G is also open as a part of log concave conjecture. This paper explores formulas on N_n (K_n-e), N_<n+1> (K_n-e), N_<n-1>(K_n・e), and N_n (K_n・e) for the two graphs K_n-e and K_n・e, which are obtained by respectively removing and contracting an edge e from a complete graph K_n with n vertices. Note that K_n・e has n- 1 vertices. In particular, we also prove that (N_n(K_n-e)^2)/(N_<n-1>(K_n-e)N_<n+1>(K_n-e))>((n-1)(n-2))/(n(n-3)) and (N_<n-1>(K_n・e)^2))/((N_<n-2>(K_n・e)N_n(K_n・e))>(n(n-2))/((n+1)(n-3)), which imply that log-concavity on N_<i-1> (G), N_i (G), N_<i+1> (G)is true for the following cases: G=K_n-e and i=n; G=K_n・e and i=n-1.
社団法人電子情報通信学会の論文
2008-06-09