De Bruijn-Good图的自同构和同态

<正> 所谓n级de Bruijn-Good图G_n是一个有向图:它有2~n个顶点,分别用2~N个二值n元素组 (a_1,a_2,…,a_n),a_i=0或1,来标记;它有2~(n+1)条弧,即对于任意两个以下形状的顶点

AUTOMORPHISMS AND HOMOMORPHISMS OF THE DE BRUIJN-GOOD GRAPH

The de Bruijn-Good graph of degree n G_n is a directed graph, with {(a_1, a_2,…, a_n)|a_i=0 or 1} as its vertex set and with {(a_1, a_2,…, a_n) → (a_2,a_3,…, a_(n+1))|a_i = 0 or 1} as its arc set, where (a_1,a_2,…, a_n) → (a_2, a_3,…, a_(n+1)) denotes an are starting at (a_1, a_2,…, a_n) and ending with (a_2, a_3,…, a_(n+1)). In this paper the following results are proved:1. G_n has only two graph automorptiisms, i.e. the identity automorphisms I and the dual automorphism D.2. There are only six two-to-one homomorphisms from G_n onto G_(n-1), denoted by where D is the dual automorphism of G_(n-1) and