| 講演抄録／キーワード |
| 講演名 |
2005-09-15 09:25
バブルソートグラフのedge-bipancyclicityとedge-fault-tolerant bipancyclicity
○菊地洋右（JST）・荒木 徹（岩手大） |
| 抄録 |
（和） |
二部グラフ$G$は，$4 \leq l \leq |V(G)|$である全ての偶数$l$に対して，
長さ$l$のサイクルを持つときbipancyclicであるという．
また，任意の偶数$l$と任意の辺$e$に対して，$G$が辺$e$を含む長さ$l$の
サイクルを含むならば，$G$はedge-bipancyclicであるという．
本論文では，バブルソートグラフ$B_n$は$n \geq 4$のときbipancyclicであ
り，さらに$n \geq 5$のときedge-bipancyclicであることを証明する．
また$B_n$に辺の故障がある場合を考え，$n \geq 4$のときに任意の辺の集
合$F$，$|F| \leq n-3$，に対して$B_n-F$がbipancyclicであることを証明
する．
$B_n$は$(n-1)$正則であるので，辺の故障の数に関してこの結果は最適であ
る． |
| （英） |
A bipartite graph $G$ is bipancyclic if $G$ has a cycle of length
$l$ for every even $4 \leq l \leq |V(G)|$.
For a bipancyclic graph $G$ and any edge $e$, $G$ is
edge-bipancyclic if $e$ lies on a cycle of any even length $l$ of
$G$.
In this paper, we show that the bubble-sort graph $B_n$ is
bipancyclic for $n \geq 4$, and also show that it is
edge-bipancyclic for $n \geq 5$.
Assume that $F$ is the subset of $E(B_n)$.
We prove that $B_n-F$ is bipancyclic, when $n \geq 4$ and
$|F| \leq n-3$.
Since $B_n$ is a $(n-1)$-regular graph, this result is optimal in the
worst case. |
| キーワード |
（和） |
バブルソートグラフ / bipancyclic / edge-bipancyclic / ハミルトニアンサイクル / 耐故障性 / / / |
| （英） |
Bubble-sort graph / bipancyclic / edge-bipancyclic / hamiltonian cycle / fault-tolerance / / / |
| 文献情報 |
信学技報, vol. 105, no. 273, COMP2005-28, pp. 1-7, 2005年9月. |
| 資料番号 |
COMP2005-28 |
| 発行日 |
2005-09-08 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
COMP |
| 開催期間 |
2005-09-15 - 2005-09-15 |
| 開催地（和） |
大阪大学 豊中キャンパス |
| 開催地（英） |
Osaka Univ., Toyonaka Campus |
| テーマ（和） |
|
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
COMP |
| 会議コード |
2005-09-COMP |
| 本文の言語 |
英語（日本語タイトルあり） |
| タイトル（和） |
バブルソートグラフのedge-bipancyclicityとedge-fault-tolerant bipancyclicity |
| サブタイトル（和） |
|
| タイトル（英） |
Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
バブルソートグラフ / Bubble-sort graph |
| キーワード(2)（和/英） |
bipancyclic / bipancyclic |
| キーワード(3)（和/英） |
edge-bipancyclic / edge-bipancyclic |
| キーワード(4)（和/英） |
ハミルトニアンサイクル / hamiltonian cycle |
| キーワード(5)（和/英） |
耐故障性 / fault-tolerance |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
菊地 洋右 / Yosuke Kikuchi / キクチ ヨウスケ |
| 第1著者 所属（和/英） |
独立行政法人科学技術振興機構今井量子計算機構プロジェクト (略称： JST)
ERATO QCI Project, Japan Science and Technology Agency (略称： JST) |
| 第2著者 氏名（和/英/ヨミ） |
荒木 徹 / Toru Araki / アラキ トオル |
| 第2著者 所属（和/英） |
岩手大学 (略称： 岩手大)
Iwate University (略称： Iwate Univ.) |
| 第3著者 氏名（和/英/ヨミ） |
/ / |
| 第3著者 所属（和/英） |
(略称： )
(略称： ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2005-09-15 09:25:00 |
| 発表時間 |
35分 |
| 申込先研究会 |
COMP |
| 資料番号 |
COMP2005-28 |
| 巻番号（vol） |
vol.105 |
| 号番号（no） |
no.273 |
| ページ範囲 |
pp.1-7 |
| ページ数 |
7 |
| 発行日 |
2005-09-08 (COMP) |