关于有向自补图的构造(Ⅱ)  

Construction of selfcomplementary digraphs (Ⅱ)

作　　者：张运清[1] 魏暹荪[1] 陈耀俊[1] 

机构地区：[1]陕西师范大学数学系

出　　处：《陕西师范大学学报（自然科学版）》1998年第1期20-24,共5页Journal of Shaanxi Normal University：Natural Science Edition

摘　　要：设Ｄ是有向自补图，Ｖ（Ｄ）＝｛１，２，…，ｎ｝，Ｄ与Ｄｃ之间的同构映射可以表示为Ｖ（Ｄ）上的一个置换σ，记为σ（Ｄ）＝Ｄｃ．若把置换写成不相交轮换的乘积，且σ１和σ２有相同的轮换结构，就有｛Ｄ｜σ１（Ｄ）＝Ｄｃ｝＝｛Ｄ｜σ２（Ｄ）＝Ｄｃ｝．因此，如果对具有不同轮换结构的ｎ阶置换σ，能构造出∪σ｛Ｄ｜σ（Ｄ）＝Ｄｃ｝，就可以构造出所有ｎ阶有向自补图．本文给出了有向自补图的构造方法，并讨论了有向自补图的结构性质．Let D be a selfcomplementary digraph with V(D)={1,2,…,n}, then the isomorphism between D and Dc can be represented as a permutation, σ, on the set V(D), σ(D)=Dc and it is assumed that all permutations are expressed as the product of disjoint cycles. As the labeling of the vertices is immaterial, it is apparent that, if σ1 and σ2 have the same cycle structure, then {D|σ1(D)=Dc}={D|σ2(D)=Dc}. Consequently, if for permutations on n symbols, ∪ σ{D|σ(D)=Dc}, where the union is taken over all possible cycle structures, then all selfcomplementary digraphs will be found with n vertices. And a new mathod is given for the construction of selfcomplementary digraphs and results concerning structural properties of selfcomplementary digraphs are presented.

关 键 词：有向自补图 自补置换 轮换 有向图 

分 类 号：O157.5[理学—数学]