バブルソートグラフのedge-bipancyclicityとedge-fault-tolerant bipancyclicity
スポンサーリンク
概要
- 論文の詳細を見る
二部グラフGは, 4≦l≦|V(G)|である全ての偶数lに対して, 長さlのサイクルを持つときbipancyclicであるという.また, 任意の偶数lと任意の辺eに対して, Gが辺eを含む長さlのサイクルを含むならば, Gはedge-bipancyclicであるという.本論文では, バブルソートグラフB_nはn≧4のときbipancyclicであり, さらにn≧5のときedge-bipancyclicであることを証明する.またB_nに辺の故障がある場合を考え, n≧4のときに任意の辺の集合F, |F|≦n-3, に対してB_n-Fがbipancyclicであることを証明する.B_nは(n-1)正則であるので, 辺の故障の数に関してこの結果は最適である.
- 社団法人電子情報通信学会の論文
- 2005-09-08
著者
-
荒木 徹
岩手大学 工学部 情報システム工学科
-
荒木 徹
岩手大学工学部情報システム工学科
-
菊地 洋右
津山工業高等専門学校 情報工学科
-
菊地 洋右
独立行政法人科学技術振興機構今井量子計算機構プロジェクト
-
菊池 洋右
群馬大学工学部情報工学系
関連論文
- 多次元分割の列挙
- 多次元分割の列挙
- 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)ラベリング
- 直並列グラフの最小ペア支配集合を求める線形時間アルゴリズム