グラフの長い通路と閉路の存在性について

关于图中长路径和闭合路径的存在性

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

平成14年度は次の予想を掲げ、以下の証明方法で予想の解決に努めた。[予想]グラフ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}}とする(証明方法)指定された頂点集合Wの頂点数|W|に関する帰納法による証明を考える。このとき、帰納法の仮定より、グラフGにはxとyを結び、指定された頂点集合の|W|-1個の頂点を通る長さmin{|V(G)|-1,2μ'(G)-2}以上の通路が存在する。(今、この状況下において最長通路Pを考える。)W⊆V(P)ならば予想は成り立つので、W〓V(P)、すなわちW-V(P)={w}としてよい。以下、wを含むG-V(P)の連結成分Hが2連結グラフである場合と、そうでない場合に分け、証明を行う。上記証明方法では、連結成分Hが2連結グラフでない場合の証明が重要となる。このとき、Hは1個以上のブロックから構成されているが、頂点w.がどのブロックに含まれているかによって、証明が非常に複雑なものとなる。また、最長通路Pの長さを求める際に、すでに最長通路P上にある頂点集合Wの位置に注意し、Pの長さを計算しなければならない。これまで、上記証明方法に従って様々な方法を試みてきたが、現在、予想の解決には至っていない。今後は上記予想のもとになっている定理を証明する際に用いた手法、すなわち、Vineと呼ばれる特殊な通路を用いた手法に改良を加えるなどして、予想の解決に努めていきたいと考えている。

Heisei 14 years to think about the first time, the following proof methods to think about the solution [Presumption] 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}}とする(证明方法)指定された顶点集合Wの顶点数|W| The proof of the law A set of vertices is defined as a set of vertices.| W|-1 {|V(G)|-1,2μ'(G)-2} or more pathways exist. (Now, under this condition, the longest path P.) W V (P) The following, w contains G-V (P) link component H 2 link The proof method mentioned above is important in the case of chain component H 2 chain. This is a very complex problem, because it is composed of more than one When the length of the longest path P is calculated, note the position of the vertex set W on the longest path P The method of proof is to try to solve the problem. In the future, we will try our best to solve the problem by using the special method.