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.

我们已经研究了反馈顶点集，分解，书籍式图表，Cayley图形表示，枚举和故障诊断，主要是在De Bruijn家族和超级皮革的图表上。1。在反馈顶点集问题上，我们表明，对于三价cayley图和与立方体相连的循环，存在最小反馈顶点集，其顺序与通用图的一般下限相同。对于二进制de bruijn图，我们已经显示存在示例，使得最小反馈顶点集的顺序大于一般图的下限。这表明在非二进制de bruijn图上的最小反馈顶点集问题上可能存在一个有趣的问题。2。在Cayley图表示上，我们显示了Kautz Digraphs的组动作图表示和二面蝴蝶的Cayley图表示。 Kautz Digraph的组动作图表示被称为一个未解决的问题，并且在很大程度上有意义地解决了该问题。3。在HyperCube变体的图形的对称性上，我们已经表明，超立方体的某些变体不是顶点及物的。