k連結グラフの指定した頂点集合を通る長い通路の存在性とハミルトン閉路に関する研究

k连通图和哈密顿循环中通过指定顶点集的长路径的存在性研究

• 批准号: 15740078
• 负责人: 弘畑 和秀
• 金额: $ 0.7万
• 依托单位: Ibaraki National College of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15740078/
• 关键词: グラフ; 頂点; 通路; 閉路; 次数; 長さ; k連結

平成16年度は次の予想1,2を掲げ、以下の証明方法で予想の解決に努めた。[予想1]グラフGがk連結グラフ(k≧4)ならば、Gには任意の2頂点x,yを結び、k-1個の頂点からなる頂点集合W(x,yは含まない)を通る長さmin{|V(G)|-1,2μ'(G)-2}以上の通路が存在する。ここでμ'(G)=min{max{d(u),d(v)}:d(u,v)=2,u,v∈V(G)-{x,y}}とする。[予想2]グラフGがk連結グラフ(k≧3)ならば、Gには任意のk個の頂点を通る長さmin{|V(G)|,2μ(G)}以上の閉路が存在する。ここでμ(G)=min{max{d(u),d(v)}:d(u,v)=2,u,v∈V(G)}とする。[証明方法]指定した頂点集合Wの頂点数|W|に関する帰納法による証明を考える。このとき、帰納法の仮定により、グラフGには指定した頂点集合の|W|-1個の頂点を通る長い通路が存在することがわかる。ここで最長通路Pを考え、W⊆V(P)ならば予想は成り立つので、W〓V(P)、すなわちW-V(P)={w}としてよい。以下、wを含むG-V(P)の連結成分Hの中にwを通る長い通路を見つけ、最長通路Pの長さを求める。上記証明方法で連結成分Hの中にwを通る長い通路を見つけるため様々な定理の拡張などを考え研究を行ってきたが、wが連結成分Hのどのブロックに含まれているかによって、証明が非常に複雑なものとなり、現在、予想の解決には至っていない。今後はVineと呼ばれる特殊な通路を用いた手法に改良を加えるなどして、予想の解決に努めていきたいと考えている。

Heisei 16 years to think about 1,2, the following proof methods to think about the solution [Presumption 1] G k (k $> 4)| V(G)|-1,2μ'(G)-2} or more pathways exist.ここでμ'(G)=min{max{d(u),d(v)}:d(u,v)=2,u,v∈V(G)-{x,y}}とする。[Presumption 2] G k k G k G k k k| V(G)|, 2 μ(G)} above the existence of closed circuit.ここでμ(G)=min{max{d(u),d(v)}:d(u,v)=2,u,v∈V(G)}とする。[Proof method] Specify the number of vertices in vertex set W| W| The proof of the law A set of vertices is defined by the set of vertices.| W|-1 Vertex is connected to the long middle path and exists. The longest path P, W V (P), W V (P) V (P)={w} The following, w contains G-V(P) and the link component H w pass long path see, the longest path P find. The above proof method is used to prove that the link component H has a long path, and the link component H. In the future, we will try our best to improve the special channel.