完全独立全域木の十分条件について
スポンサーリンク
概要
- 論文の詳細を見る
T_1, T_2をグラフGの二つの全域木とする.Gの任意の2頂点u, vに対して,T_1上のu-vパスとT_2上のu-vパスが内素であるとき,T_1とT_2は完全独立であるという.本報告では,グラフに二つの完全独立全域木が存在するための必要十分条件を示す.その特徴付けを用いて,さらに二つの十分条件を証明する.まず,n頂点のグラフの最小次数がn/2以上であるなら,そのグラフに二つの完全独立全域木が存在することを示す.続いて,Gが2連結ならその2乗G^2に二つの完全独立全域木が存在することを示す.これらの条件は,いずれもグラフにハミルトニアンサイクルが存在するための十分条件として知られている条件である.
- 2012-05-07
著者
関連論文
- k木における完全独立全域木について
- k木における完全独立全域木について
- とびらの言葉
- Bipartite permutation graphのL(2,1)ラベリング
- 直並列グラフの最小ペア支配集合を求める線形時間アルゴリズム
- 局所完全ダイグラフの独立双方向支配集合問題について
- 完全独立全域木の十分条件について
- A-004 区間グラフの向き付けにおける双方向支配(アルゴリズム,A分野:モデル・アルゴリズム・プログラミング)
- 完全独立全域木の十分条件について