節点数がn、辺数が「(3-2√<2>)n^2+n-(7-2√<2>)/(2√<2>)」以上の単純無向グラフにおける連結全域部分グラフの個数系列の単峰性に関する証明

概要

論文の詳細を見る
n個の節点とm本の辺をもつ単純無向グラフG=(V,E)において,i(n-1≦i≦m)本の辺を有するGの連結全域部分グラフの個数をN_iで表す.系列N_<n-1>,N_n,…,N_mが単峰形(unimodal),あるいは,対数的凹形(log-concave)であるか否かは未解決問題としてよく知られている[15][9].ここで,実数系列a_0,a_1,…,a_mを,ある整数i(0≦i≦m)に対してa_0≦a_1≦…≦a_i≧a_<i+1>≧…≧a_mを満たすときに単峰形といい,すべての整数i(0≦i≦m)に対してa^2_i≧a_<i-1>a_<i+1>を満たすときに対数的凹形という.本論文では,節点数がn,辺数が「(3-2√<2>)n^2+n-(7-2√<2>)/(2√<2>)」以上グラフGに対して系列N_<n-1>,N_n,…,N_mは単峰形であることを証明する.また,節点数が7以下のグラフGに対して系列N_<n-1>,N_n,…,N_mは対数的凹形であることを証明する.
社団法人電子情報通信学会の論文
2007-09-13