偶错位图的张量幂的最大独立集和自同构群

Maximum-size independent sets and automorphism groups of tensor powers of the even derangement graphs

若An是X:={1,2,...,n}上的偶置换构成的交错群,εn是X上的偶错位集,则Cayley图AΓn:=Γ(An,εn)称为偶错位图.令AΓqn为q个AΓn的张量幂.在本文中,我们研究了AΓqn的连通性、直径、独立数、团数、色数和最大独立集等性质.利用AΓqn最大独立集的结果,我们完全确定了AΓqn的自同构群的结构.

Let An be the alternating group of even permutations of X ：= {1, 2, . . . , n} and En the set of even derangements on X. Denote by AΓqn the tensor product of q copies of AΓn, where the Cayley graph AΓn ：= Γ（An, En） is called the even derangement graph. In this paper, we intensively investigate the properties of AΓqn including connectedness, diameter, independence number, clique number, chromatic number and the maximumsize independent sets of AΓqn. By using the result on the maximum-size independent sets AΓqn, we completely determine the full automorphism groups of AΓqn.