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

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

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.