权益分类	功能权益	普通用户	{{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图表示法上，我们给出了Kautz有向图的群动作图表示法和二面体蝴蝶的Cayley图表示法。Kautz有向图的群体行动图表示一直是一个未解决的问题，该问题的解决具有重要意义。在超立方体变异体图的对称性上，我们证明了超立方体的一些变异体不是顶点传递的。