| 講演抄録／キーワード |
| 講演名 |
2004-09-17 15:00
Kautzダイグラフのgroup action graph表現
○田中勇樹・柴田幸男（群馬大） |
| 抄録 |
（和） |
De BruijnダイグラフやShuffle-Exchangeダイグラフは相互結合網の有用なモデルとして知られている．それらのグラフはそれぞれButterflyグラフやCube-Connected CyclesのCayley cosetグラフとして表すことが可能であり，それぞれのgroup action graphでもある．
Kautz ダイグラフは定義や性質がde Bruijnダイグラフに類似しており，$d$正則であるので，あるCayleyダイグラフのCayley cosetグラフ，あるいはgroup action graphとなることが分かっているが，具体的なCayleyダイグラフの構造については未知であった．本稿ではKautz ダイグラフのgroup action graph表現を与え，Kautz ダイグラフをgroup action graphとして持つようなCayleyダイグラフのクラスを与える． |
| （英） |
De Bruijn digraphs and shuffle-exchange graphs are known to be useful
models for interconnection networks. They can be represented as Cayley
coset graphs of the wrapped butterfly graph and the cube-connected
cycles, respectively. The Kautz digraphs have the similar definitions
and properties to de Bruijn digraphs. It is $d$-regular and strongly
$d$-connected, thus it is a GAG and a coset digraph. In this paper, we
will show a new representation of the Kautz digraph and settle the
open problem posed by M.-C. Heydemann. |
| キーワード |
（和） |
Cayley ダイグラフ / Kautz ダイグラフ / 群のwreath積 / group action graph / / / / |
| （英） |
Cayley digraph / Kautz digraph / wreath product of groups / group action graph / / / / |
| 文献情報 |
信学技報, vol. 104, no. 317, COMP2004-32, pp. 49-56, 2004年9月. |
| 資料番号 |
COMP2004-32 |
| 発行日 |
2004-09-10 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|