文献

J-GLOBAL ID：201702289414415728   整理番号：17A0274149

一般化de Bruijnダイグラフと一般化Kautzダイグラフの拡張について

著者 (3件)： 菊地洋右 (津山工高専) ,  松本猛 (津山工高専) ,  河村奈々 (津山工高専)
資料名： 電子情報通信学会論文誌 A(Web)
巻： J100-A  号： 2  ページ： 125-133 (WEB ONLY)  発行年： 2017年02月01日 
JST資料番号： U0470A  ISSN： 1881-0195  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では一般化de Bruijnダイグラフと一般化Kautzダイグラフをそれぞれ拡張したダイグラフを導入する。そして,それらのダイグラフの同型性と支配数について考察する。導入するダイグラフをs拡張一般化de BruijnダイグラフGB(n,d,k),s拡張一般化KautzダイグラフGK(n,d,k)とよぶ。GB(n,d,k)が一般化de BruijnダイグラフGB(n,d)と同型となる条件,GK(n,d,k)が一般化KautzダイグラフGK(n,d)と同型となる条件について述べる。また,異なるkとk′に対してGB(n,d,k)とGB(n,d,k′)が同型となる条件,同様にGK(n,d,k)とGK(n,d,k′)が同型となる条件について考察する。更に,GB(n,d,k)とGK(n,d,k)の支配数についても考察し,d+1|nの場合についてそれぞれのダイグラフに対してsolutionをもつ条件を示す。(著者抄録)

シソーラス用語： *有向グラフ ,  同形写像 ,  *グラフ理論
準シソーラス用語： *ダイグラフ ,  *Kautzダイグラフ ,  *de Bruijnダイグラフ

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (15件)：

• N.G. de Bruijn, “A combinatorial problem,” Proc. Kon. Nederl. Akad. Wetensch, Ser. A, vol.49, pp.758-764, 1946.
• C. Boucher, A. Bowe, T. Gagie, S.J. Puglisi, and K. Sadakane, “Variable-Order de Bruijn Graphs,” Proc. IEEE Data Compression Conference, pp.383-392, 2015. DOI:10.1109/DCC.2015.70
• W.G. Bridges and S. Toueg, “On the impossibility of directed Moore graphs,” J. Combinatorial Theory, Ser. B, vol.29, pp.339-341, 1980. DOI:10.1016/0095-8956(80)90091-X
• D.Z. Du and F.K. Hwang, “Generalized de Bruijn digraphs,” Networks, vol.18, pp.27-38, 1988.
• J.-C. Bermond and C. Peyrat, “De Bruijn and Kautz networks: a competitor for the hypercube?,” Hypercube and Distributed Computers, pp.279-293, 1989.

タイトルに関連する用語 (3件)： 一般化 ,  ダイグラフ ,  拡張