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

山西师范大学学报 (自然科学版) 第21卷第 1期 JournalofShanxiNormalUniversity V01．21 No．1 2007年 3月 NaturalScienceEdition Mar．2Oo7 文章编号：1009-4490(2007)01-0010-03 2一重 自补图和有 向自补图的几个性质 马杰 良，王玉珏，李鑫丽 (南京信息工程大学电子与信息工程学院，江苏 南京210044) 摘 要：本文讨论了2．重 自补图和有向自补图的连通性以及 2·重自补图的直径 ，同时以白补置换作为 工具研究了当2．重自补图或有向自补图被分成两个连通分支后，这两个连通分支之间的边数与顶点数 之间的关系． 关键词：2．重 自补图；有向自补图；自补置换；度向量序列 中图分类号：0157．5 文献标识码：A 1 相关定义和记号 本文中的有向图都是指有限、无 自环且没有重弧的有向图，一般情况下用D来表示．令 V(D)= {M。， M，…，}，则序列仃={()(萎)_．fd；‘l1Jl称作有向图。的度偶序列，其中d=d，d=d反·过来， 若仃={(：：)(：：)…(Z))是某个有向图的度偶序列，则称仃是可有向图实现的· 设D是一个有向图，则D的补图用D表示，这时V(D)=V(D)，并且对于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 设 。是一个有向自补图，仃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)的顶点，—di=(兰1，则(d2．．．)是D的度向量序列，那么 ( —d — p_l d1)是的度向量序列．这里我们用表示(兰1； (4)d + 。一=df+ 。一=P一1． 注：关于度向量序列的大小秩序我们有以下的规定：设订(。){、rslll，I、rl…())，若ri，我们称 ()()；若 ，s，称()()；若 ，si，称()()· 一 般情况下我们称 7r= ( ．． )是有向图D的度向量序列要求 ≤d2≤… ≤dp． 引理2 设D是一个有向自补图，那么D的基础图是2．重 自补图． 这个结论的逆不成立． 3 主要结论 定理 l 任一2-重 自补图是连通的，任一有向自补图是弱连通的． 证明： 设G是一个有限的2-重 自补图，G是不连通的，设G。、 是它的两个连通分支，以下我们将证 明G是连通的． 设 和 是 (G)中任意两点，它们在G中是不相邻的，即(，)甓E(G)，由2一重 自补图的定义可知， 与 在G中有两条边相连，因而 、在G中属于同一个连通