講演抄録/キーワード |
講演名 |
2005-10-18 14:30
辺の故障があるバブルソートグラフのhamiltonian laceability ○荒木 徹(岩手大)・菊地洋右(JST) |
抄録 |
(和) |
$n$次元バブルソートグラフは二部グラフ,$(n-1)$正則,かつ$n!$個の頂点を持つグラフである.
本論文では,$n \geq 4$のとき,任意の頂点$v$に対して,$B_n-v$が$v$と異なる二部分割の任意の2頂点間を結ぶハミルトニアンパスを持つことを証明する.また$B_n$に辺の故障がある場合を考え,$n \geq 4$のときに任意の辺の集合$F$,$|F| \leq n-3$,に対して,$B_n-F$が異なる二部分割にある任意の2頂点間を結ぶハミルトニアンパスを持つことを示す.さらに,$B_n-F$が同じ二部分割にある任意の2頂点間を結ぶ長さ$n!-2$のパスを持つことを示す.辺の故障の数に関してこの結果は最適である. |
(英) |
It is known that the $n$-dimensional bubble-sort graph $B_n$ is bipartite, $(n-1)$-regular, and has $n!$ vertices.
We first show that, for any vertex $v$, $B_n-v$ has a hamiltonian path between any two vertices in the same partite set without $v$. Let $F$ be a subset of edges of $B_n$. We next show that $B_n-F$ has a hamiltonian path between any two vertices of different partite sets if $|F|$ is at most $n-3$. Then we also prove that $B_n-F$ has a path of length $n!-2$ between any pair of vertices in the same partite set. |
キーワード |
(和) |
/ / / / / / / |
(英) |
bubble-sort graphs / hamiltonian laceability / strongly hamiltonian laceability / hyper hamiltonian laceability / hamiltonian cycle / fault-tolerance / / |
文献情報 |
信学技報, vol. 105, no. 343, COMP2005-40, pp. 29-35, 2005年10月. |
資料番号 |
COMP2005-40 |
発行日 |
2005-10-11 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|