Deza有向图的构作

1、摘要:讨论了Deza 有向图的构作,通过两个Deza 有向图的直积得到新的Deza 有向图,并证明出了它们所应满足的条件。关键词:有向图;Deza 有向图;直积中图分类号:O157.5文献标识码:A文章编号:1673-1018(201001-0043-03Construction of Deza digraphsGUO Hai-xia ,GUO Jin-ping ,BIAN Xiao-li(School of Science ,Tianjin University of Technology and Education ,Tianjin 30022,China Abstract :The co

2、nstruction of Deza digraphs is discussed in this paper.By two of the direct product of a di -rected graph ,the new Deza digraph is obtained and the conditions are proved.Key words :digraph ;DDG ;directed product收稿日期:2009-07-09基金项目:天津工程师范学院科研计划项目(KJ0819.作者简介:郭海霞(1979,女,讲师,硕士,研究方向为代数组合.第20卷第1期2010年3月天

3、津工程师范学院学报JOURNAL OF TIANJIN UNIVERSITY OF TECHNOLOGY AND EDUCATIONDeza 有向图的构作郭海霞,郭金萍,边小丽(天津工程师范学院理学院,天津300222Vol.20No.1Mar.2010Deza 有向图1的概念是由A.Deza 和M.Deza 首先给出的,如果一个有向图是正则的,并且它的任意两点共同的出度的点数至多有两种可能,于是就把这类图称为Deza 有向图。作为强正则图的一种推广,在1999年,Erickson 等人介绍了Deza 有向图是一个广义的强正则图2。他们介绍了构作Deza 图的几个方法,并形成了一些基本的理论。

4、由于强正则图作为一类特殊的距离正则图,在2003年3,张更生老师提出了一个弱距离正则有向图满足一些充分必要条件时就是Deza 有向图。Deza 有向图概念是通过对广义Deza 有向图和一些有向图的基本理论的描述来完成的4。本文讨论Deza 有向图的构作,通过Deza 有向图的直积来构作Deza 有向图,证明两个Deza 有向图通过直积构作仍为Deza 有向图的充要条件。1相关定义及命题定义1设是n 个顶点的一个正则图,A 为的邻接阵,称作是一个(n ,k ,b ,c -Deza 图或简记为DG ,若:A 2=kI +bB +cC B 、C 为某(0,1阵,满足B +C +I =J ,其中J 为

5、n 阶全1阵,且I 为n 阶单位阵5。定义2设是n 个顶点的一个正则有向图,邻接阵为A ,围长至少为3,称为(n ,k ,-正规正则有向图或简记为NRD ,若:AA =kI +(A +A +(J -I -A -A 其中,A 是A 的转置。定义3设是n 个顶点的一个正则有向图,邻接阵为A ,称作是一个(n ,k ,b ,c -Deza 有向图或DDG ,若:AA =kI +bB +cC (b c B 、C 为某对称的(0,1阵且满足B +C +I =J 。定义4设G 为有限群,S 哿G ,且S 中不含有单位元。定义G 关于S 的Cayley 有向图=Cay (G ,S ,其中V =G ,A =(

6、x ,sx |x G ,s S 并且是连通的当且仅当G =S 。天津工程师范学院学报第20卷于是可以从组合方法得到Deza 有向图的一个等价定义:定义5一个具有n 个顶点的正则有向图是(n ,k ,b ,c -DDG 有向图,若u ,v V ,|N u ,v |=b 或c ,u vk,u =v 这里N u ,v =u +v +(u +、v +表示顶点u 、v 的出度。定义6设1、2为有向图,从1到2的直积1×2是以(u 1,u 2|u 1V 1,u 2V 2为顶点集且以(u 1,u 2,(u 1,u 2|(u 1,u 1A 1,u 2=u 2或(u 2,u 2A 2,u 1=u 1为

7、弧集的有向图。引理1对于一些特殊值的(n ,k ,b ,c ,以下命题成立:(i 不存在(n ,k ,k ,k -DDG 。(ii 如果是一个(n ,k ,0,0-DDG 图,那么k =1。例如,是一个有向圈C n 。(iii 如果是一个(n ,k ,k-1,k -1-DDG ,k 2,那么是一个有n 个顶点的完全图,即=K n 。(iv 如果是一个(n ,k ,b ,c -DDG ,n =2k -c ,那么=K n 。2主要结论定理1令1是一个(n ,k ,b ,c -DDG ,2是一个(n ,k ,b ,c -DDG ,令=1×2则的价为k +k 。证明坌(u 1,v 1V ,由

8、于1的价是k ,不妨设(u 1,u 0,(u 1,u 2,(u 1,u k A 1,而2的价是k ,这里不妨设(v 1,v 0,(v 1,v 2,(v 1,v k A 2,则中点(u 1,v 1的邻接点示意如下:所以的价为k +k 。定理2令1是一个(n ,k ,b ,c -DDG ,2是一个(n ,k ,b ,c -DDG ,令=1×2为DDG ,则1、2为下列情况之一:(i 1为(n ,1,0,0-DDG ,2为(n ,1,0,0-DDG ;(ii 1为(n ,k ,0,c -DDG ,2为(n ,k ,0,c -DDG ;(iii1为(n ,k ,c ,c -DDG ,2为(n

9、 ,k ,c ,c -DDG ;(iv 1为(n ,k ,0,c -DDG ,2为(n ,k ,0,c -DDG ;(v 1为(n ,1,0,0-DDG ,2为(n ,k ,0,c -DDG 。证明对于的两个不同的顶点u =(u 1,v 1,v =(u 2,v 2:(i 当u 1=u 2时,|N u ,v |=|N v 1,v 2|而|N v 1,v 2|=b 或c ;(ii 当v 1=v 2时,|N u ,v |=|N u 1,u 2|而|N u 1,u 2|=b 或c 。|N u ,v |=|N v 1,v 2|,若u 1=u 2|N u 1,u 2|,若v 1=v 20,其坌坌坌坌坌坌坌

10、坌坌坌坌它(1通过定义5可知如果是DDG 图,当且仅当|M |2(其中M =b ,b ,c ,c ,0。如果c =c ,那么M =b ,b ,c ,0,有c =c =0且b =b =0或c =c =0,b =b =0或c =c =b =b 0。(i c =c =0且b =b =01为(n ,k ,0,0-DDG ,2为(n ,k ,0,0-DDG 。由引理1可知1、2都是有向圈,即1为(n ,1,0,0-DDG ,2为(n ,1,0,0-DDG 。如:1为(3,1,0,0-DDG ,2为(3,1,0,0-DDG 。(ii c =c 0且b =b =01为(n ,k ,0,c -DDG ,2为(

11、n ,k ,0,c -DDG 。如:1为(4,2,0,1-DDG ,2为(5,2,0,1-DDG 。(iii c =c =b =b 01为(n ,k ,c ,c -DDG ,2为(n ,k ,c ,c -DDG ,其中n c +2,n c +2。如:当c =c =b =b =k -1时,1、2是两个相同的完全图。如果c c ,那么M =b ,c ,b ,c ,0,有c 0,b =b =c =0或c 0,b =b =c =0。(iv c 0且b =b =c =01为(n ,k ,0,c -DDG ,2为(n ,k ,0,0-DDG 。由引理1知2是一个有向圈。如:1为(4,2,0,1-DDG 和

12、2为(3,1,0,0-DDG 。(v c 0且b =b =c =01为(n ,k ,0,0-DDG ,2为(n ,k ,0,c -DDG 。则1是一个有向圈。如:1(5,1,0,0-DDG 和2为(5,2,0,1-DDG 。若b 、b 、c 、c 不满足上述几种情况,则有|M |3。这时并不能构作成DDG 图。u 1v 1u 1v 0u 1v 2u 1v k u 0v 1u 2v 1u k v 144··第1期3结束语从文从Deza 有向图的定义出发,将两个Deza 有向图运用直积构作出新的有向图,然后通过对其参数的计算,再利用引理1一些特殊值的(n ,k ,b ,c -D

13、DG 所得到的重要结论,找出满足Deza 有向图条件。参考文献:1DEZA A ,DEZA M.The Ridege Grahe of The M etric Polytopeand Some Rela-tives M .Polytopes :NATO ASI Series ,Kluwer Academic ,1994:359-372.2ERICKSON M ,FERNANDO S ,HAEM ERS W H.Dezagraphs :A generalization of strongly regular graphs J.Combin Des ,1999(7:359-405.3ZHANG G

14、 ,WANG K.A directed version of Deza graphs Dezadigraphs J.Australasian Journal of Combinatorics ,2003(28:239-244.4WANG K ,FENG Y.Deza digraphs J.Europ Combin ,2006(27:995-1004.5高锁刚,游宏.E1.Ed 型的距离正则图J.科学通报,2000,45(17:1816-1818.郭海霞,等:Deza 有向图的构作欢迎订阅天津工程师范学院学报天津工程师范学院学报是天津工程师范学院主办的面向国内外公开发行的综合性学术刊物,刊号CN 12-1373/Z ,ISSN 1673-1018。本刊主要刊登机械工程、自动化工程、电子工程、计算机科学与技术、职业技术教育科