抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
Gallai(1966)の良く知られた問題は,接続グラフの全ての最長経路を通過する頂点が存在するかどうかを尋ねた。これは,外部平面グラフ,円形アークグラフ,および直列並列グラフのようないくつかの特別なクラスのグラフに対して検証されているが,回答は一般的グラフに対して負である。本論文では,結合によって頂点を置き換えるならば,その答えが肯定的であることを他の結果の中で証明した。グラフの結合は最小非空エッジカットである。特に,任意の2連結グラフにおいて,頂点に入射するすべてのエッジの集合は頂点結合と呼ばれる結合である。明らかに,2連結グラフに対して,vに関して頂点結合を満たすならば,経路が頂点vを通して通過する。したがって,Gallaiの質問に対する非常に自然なアプローチは,すべての最長経路を満たす結合があるかどうかを研究することである。pは接続グラフの最長経路の長さを示す。任意の2連結グラフに対して,少なくともp-1の長さの全ての経路を満たす結合があることを示した。次に,任意の3連結グラフに対して,少なくともp-2の長さのすべての経路を満たす結合があることを証明した。k結合グラフ(k≧3)では,もしpが奇数ならば,pが偶数でt=Big[√k-2/2Big]ならば,少なくともp-t+1の長さの全ての経路を満たす結合があることを示す,ここでは,もしpが奇数であるならば,t=Big[√k-2/2Big]である。著者らの結果は,P.WuとS.McGuinnessの対応する結果のアナログ(グラフにおけるBonds交差サイクル,Combinatorica 25(4)(2005),439~450)も提供する。【JST・京大機械翻訳】
