2重自补图和有向自补图的几个性质一

《2重自补图和有向自补图的几个性质一》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、山西师范大学学报(自然科学版)第21卷第1期JournalofShanxiNormalUniversityV01．21No．12007年3月NaturalScienceEditionMar．2Oo7文章编号：1009-4490(2007)01-0010-032一重自补图和有向自补图的几个性质马杰良，王玉珏，李鑫丽(南京信息工程大学电子与信息工程学院，江苏南京210044)摘要：本文讨论了2．重自补图和有向自补图的连通性以及2·重自补图的直径，同时以白补置换作为工具研究了当2．重自补图或有向自补图被分成两个连

2、通分支后，这两个连通分支之间的边数与顶点数之间的关系．关键词：2．重自补图；有向自补图；自补置换；度向量序列中图分类号：0157．5文献标识码：A1相关定义和记号本文中的有向图都是指有限、无自环且没有重弧的有向图，一般情况下用D来表示．令V(D)={M。，M，⋯，}，则序列仃={()(萎)．_‘fd；1llJ称作有向图。的度偶序列，其中d=d，d=d·反过来，若仃={(：：)(：：)⋯(Z))是某个有向图的度偶序列，则称仃是可有向图实现的·设D是一个有向图，则D的补图用D表示，这时V(D)=V(D)，并且对

3、于V(D)中的两个顶点M和，e=(M，)EA(D)当且仅当e=(M，)隹A(D)．若D兰D则称D是有向自补图，并且D和D之间的同构映射称作有向自补置换，一般用s来表示．显然，若D是一个阶为P的有向自补图，则lA(D)l=P(P—I)／2．设A、是有向图D的两个顶点集，则我们用D[A]、D[B]分别表示由A、B导出的D的子有向图．用D[A，B]表示顶点集为AUB，弧集为A(D)中的一个端点在A中，另一个端点在B中的弧所组成的D的子有向图．文中未定义的概念与记号请参阅文献[1]和[2]．2相关引理引理-[3设。

4、是一个有向自补图，仃c。)Xd”⋯Xd[2／(喜))是。的度向量序列，则：㈩P=耋d(三)；(2)d+d=d+d=P一1，这里d=d吉(M)，d=d云(Mi)，MiEV(D)；收稿日期：2006·12-24基金项目：南京信息工程大学科研启动基金资助项目(QD12)．作者简介：马杰良(1964一)，男，山西稷山人，南京信息工程大学电子与信息工程学院副教授，主要从事计算机软件理论、图论及应用研究．第1期马杰良王玉珏李鑫丽：2-重自补图和有向自补图的几个性质(3)用。，，⋯，来表示(D)的顶点，d—i=(兰1，则

5、(d2．．．)是D的度向量序列，那么—(d—p_ld1)是的度向量序列．这里我们用表示(兰1；(4)d+。一=df+。一=P一1．注：关于度向量序列的大小秩序我们有以下的规定：设订(。){、srll，I、r'l⋯())，若ri>，我们称()>()；若，s>，称()>()；若，si，称()()·一般情况下我们称7r=(．．)是有向图D的度向量序列要求≤d2≤⋯≤dp．引理2设D是一个有向自补图，那么D的基础图是2．重自补图．这个结论的逆不成立．3主要结论定理l任一2-重自补图是连通的，任一有向自补图是弱连通的

6、．证明：设G是一个有限的2-重自补图，G是不连通的，设G。、是它的两个连通分支，以下我们将证明G是连通的．设和是(G)中任意两点，它们在G中是不相邻的，即(，)甓E(G)，由2一重自补图的定义可知，与在G中有两条边相连，因而、在G中属于同一个连通分支．不妨设、∈V(G。)，而G是不连通的，所以我们有ly(G2)l>0，即至少有一个顶点∈y(G2)，使得与和都不相邻．同样由2．重自补图的定义，在G中与和都有两条边相邻，即(，)，(，)∈E(G)，这样和在G中是相邻的，由、的任意性可知，G是连通的，而G是2-重

7、自补的图，即G兰G，故G也是连通的，这与假设矛盾，所以G是连通的．由引理2知，任一有向自补图的基础图是2-重自补图，而2．重自补图是连通的，故任一有向自补图是弱连通的．定理2任一2-重自补图的直径小于或等于3．证明：设G是一个2．重自补图，但是G的直径d(G)>3，对于任意两点，∈V(G)，若、在G中不相邻，那么由2-重自补图的定义可知，、在G中有两条边相邻，即以、为端点的边有两条，由于d(G)>3，因此在G中有一点，它和、在G中都不相邻，如若不然，对于任一点)，∈V(G)，那么)，与、之间至少一点相邻，这

8、样的话d(G)≤3，这与假设相矛盾．故在G中(，u)∈E(G)，(，)∈E(G)，这样d(，)≤2，由、的任意性可知d(G)≤2，而G是2．重自补图，d(G)=d(G)，这样就与d(G)>3相矛盾，故d(G)≤3．以上的两个定理主要讨论了2-重自补图和有向自补图在连通性和直径之间的关系．以下我们将主要讨论当2-重自补图或有向自补图被分成两个连通分支后，这两个连通分支之间的边数与顶点数之间的关系．定理3设G是一个P