权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Systematization of graph operations for interconnection networks and its application to fault diagnosis

互连网络图运算系统化及其在故障诊断中的应用

基本信息

批准号：
16500006
负责人：
SHIBATA Yukio
金额：
$ 2.37万
依托单位：
Gunma University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2006
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16500006/
关键词：
de Brujin graph Kautz graph hypercube feedback vertex set interconnection network graph 相互結合網グラフの積ド・ブルーイングラフ故障診断ページナンバー trivalent Cayley graph cube-connected cycles 本型埋め込みブロードキャスト de Brui jnダイグラフ wreath積辺彩色適応型故障診断

项目摘要

We have investigated feedback vertex set, decomposition, bookembedding, Cayley graph representation, enumeration and fault diagnosis mainly on graphs of de Bruijn family and hypercubes.1. On the feedback vertex set problem, we have shown that for trivalent Cayley graphs and cube-connected cycles, there exist minimum feedback vertex sets with the order that are the same as the general lower bound for general graphs. For binary de Bruijn graph, we have shown that there exist examples such that the order of the minimum feedback vertex set is larger than the lower bound for general graphs. This suggests that there might be a interesting problem on the minimum feedback vertex set problem on nonbinary de Bruijn graphs.2. On the Cayley graph representation, we have shown the group action graph representation of Kautz digraphs and the Cayley graph representation of dihedral butterflies. The group action graph representation of Kautz digraph is known as an unsolved problem and it is largely meaningful that the problem has been settled.3. On the symmetry of graphs of variants of the hypercube, we have shown that some of variants of the hypercube are not vertex transitive.

主要研究了de Bruijn族图和超立方体图的反馈顶点集、分解、书嵌入、Cayley图表示、计数和故障诊断.关于反馈点集问题，我们证明了对于三价Cayley图和立方连通圈，存在阶数与一般图的一般下界相同的最小反馈点集.对于二元de Bruijn图，我们证明了存在最小反馈点集的阶大于一般图的阶的下界的例子。这表明在非二进制de Bruijn图上可能存在一个有趣的最小反馈点集问题.在Cayley图表示上，我们给出了考茨有向图的群作用图表示和二面体蝴蝶的Cayley图表示。有向考茨图的群作用图表示是一个尚未解决的问题，该问题的解决具有重要意义.关于超立方体的变形图的对称性，我们证明了超立方体的某些变形图不是点传递的。