辺に故障のあるバブルソートグラフのhamiltonian laceability
スポンサーリンク
概要
- 論文の詳細を見る
n次元バブルソートグラフは二部グラフ, (n-1)正則, かつn!個の頂点を持つグラフである.本論文では, n≧4のとき, 任意の頂点vに対して, B_n-vがvと異なる二部分割の任意の2頂点間を結ぶハミルトニアンパスを持つことを証明する.またB_nに辺の故障がある場合を考え, n≧4のときに任意の辺の集合F, |F|≦n-3, に対して, B_n-Fが異なる二部分割にある任意の2頂点間を結ぶハミルトニアンパスを持つことを示す.さらに, B_n-Fが同じ二部分割にある任意の2頂点間を結ぶ長さn!-2のパスを持つことを示す.辺の故障の数に関してこの結果は最適である.
- 社団法人電子情報通信学会の論文
- 2005-10-11
著者
-
荒木 徹
岩手大学 工学部 情報システム工学科
-
荒木 徹
岩手大学工学部情報システム工学科
-
菊地 洋右
津山工業高等専門学校 情報工学科
-
菊地 洋右
独立行政法人科学技術振興機構今井量子計算機構プロジェクト
-
菊池 洋右
群馬大学工学部情報工学系
関連論文
- 多次元分割の列挙
- 多次元分割の列挙
- k木における完全独立全域木について
- オイラー路の列挙
- k木における完全独立全域木について
- グラフ的列の列挙
- 互換集合から生成されるCayleyグラフのbipancyclicity
- 辺に故障のあるバブルソートグラフのhamiltonian laceability
- バブルソートグラフのedge-bipancyclicityとedge-fault-tolerant bipancyclicity
- Caterpillarの列挙アルゴリズム
- Generalized de Bruijn digraphの同型因子分解
- de Bruijnグラフの独立点集合について
- クロネッカー積グラフのデカルト積グラフによる同型因子分解
- de Bruijnダイグラフのサイクル分解について
- ハイパーキューブとパスの積グラフの分解について
- グラフにおける距離に基ずくグラフの積
- 集合の被覆の列挙
- 整数分割の列挙(セッション3)
- ハイパーキューブ族のネットワークにおける適応型故障診断について
- バタフライ上の最適な検査数によるadaptiveな故障診断
- 故障のあるRecursive Circulantへのサイクルの埋め込み
- バタフライネットワークにおけるadaptiveな故障診断
- Cayleyグラフ上の最適な故障診断システムの構成
- グラフ演算による最適な故障診断可能システムの構成 (計算理論とアルゴリズムの新展開)
- グラフ演算による故障診断可能システムの最適構成
- 完全二部グラフの同型因子分解II:分解
- 完全二部グラフの同型因子分解I:整除性
- A-42 Bipartiteグラフのdirect productにおける素因子分解の非一意性について(グラフアルゴリズム(3),A.アルゴリズム・基礎)
- アダマールグラフのグラフ彩色ゲームに対する量子プロトコル
- Bipartite permutation graphのL(2,1)ラベリング
- 直並列グラフの最小ペア支配集合を求める線形時間アルゴリズム