Prime Labellingの研究

Vを頂点集合,Eを辺集合とする無向グラフG=(V,E)を以下考える。ただし,|V|=n<∞とする.グラフGに対して,頂点aと頂点bが隣接しているとき,l_aとl_b(1【less than or equal】l_a【less than or equal】n,1【less than or equal】l_b【less than or equal】n)が互いに素になるようにラベルづけすることをPrime Labellingと言う.ただし,l_aとl_bは,頂点aと頂点bのラベルづけを表す.グラフGがPrime Labelling可能のとき,GをPrime Graphという.また,ラベルづけを奇数に限った場合をOdd Prime Labellingという.本研究では,Odd Prime Labellingを主として取り扱った.辺の数が最大な連結グラフである完全グラフK_n,n【greater than or equal】4はPrime Graphではない.そこで,まず連結グラフで辺の数がもっとも少ない木(Tree)についてPrime Labellingの可能性を調べたい.A={a_1,a_2,…,a_m}とおく.ただし,a_1,a_2,…,a_mは連続した正の整数とする.Aの元bがAの残りの元と互いに素であるとき,bは,Relative Prime Numberと言う.16以下のmに対しては,Aの中に必ずRelative Prime Numberがあることが知られている.このことを利用して,FuとHuangはP(m,k)(k【less than or equal】14)はPrime Graphであることをしめしている.本研究では,連続した奇数列および上記のAにおいて,a_i-a_<i-1>=tの場合にRelative Prime Numberの存在性について,ある種の結果が得られた.t=P^<l1>_1P^<l2>_2…P^<lf>_fとおく.ただし,P_1,P_2,…,P_fは相異なる素数とする.a_1があるP_iで割り切れるときは,明らかに,Aの中にRelative Prime Numberは存在しない.また,a_1がすべてのP_i(1【less than or equal】i【less than or equal】f)で割りきれないときには,十分大きなmに対しては,つねにRelative Prime Numberが存在しないような列a_1,a_2,…,a_mが存在することが分かった.

Vを頂点集合,Eを辺集合とする無向グラフG=(V,E)を以下考える。ただし,|V|=n<∞とする.グラフGに対して,頂点aと頂点bが隣接しているとき,l_aとl_b(1【less than or equal】l_a【less than or equal】n,1【less than or equal】l_b【less than or equal】n)が互いに素になるようにラベルづけすることをPrime Labellingと言う.ただし,l_aとl_bは,頂点aと頂点bのラベルづけを表す.グラフGがPrime Labelling可能のとき,GをPrime Graphという.また,ラベルづけを奇数に限った場合をOdd Prime Labellingという.本研究では,Odd Prime Labellingを主として取り扱った.辺の数が最大な連結グラフである完全グラフK_n,n【greater than or equal】4はPrime Graphではない.そこで,まず連結グラフで辺の数がもっとも少ない木(Tree)についてPrime Labellingの可能性を調べたい.A={a_1,a_2,…,a_m}とおく.ただし,a_1,a_2,…,a_mは連続した正の整数とする.Aの元bがAの残りの元と互いに素であるとき,bは,Relative Prime Numberと言う.16以下のmに対しては,Aの中に必ずRelative Prime Numberがあることが知られている.このことを利用して,FuとHuangはP(m,k)(k【less than or equal】14)はPrime Graphであることをしめしている.本研究では,連続した奇数列および上記のAにおいて,a_i-a_<i-1>=tの場合にRelative Prime Numberの存在性について,ある種の結果が得られた.t=P^<l1>_1P^<l2>_2…P^<lf>_fとおく.ただし,P_1,P_2,…,P_fは相異なる素数とする.a_1があるP_iで割り切れるときは,明らかに,Aの中にRelative Prime Numberは存在しない.また,a_1がすべてのP_i(1【less than or equal】i【less than or equal】f)で割りきれないときには,十分大きなmに対しては,つねにRelative Prime Numberが存在しないような列a_1,a_2,…,a_mが存在することが分かった.