论文部分内容阅读
竞争图的概念是由Cohen在研究食物链网络模型时提出的,被广泛应用于生态系统的研究.除此之外,它还被应用在噪声信道下通信的研究和设定无线电或电视发射机频道等问题.因而,有向图的竞争图越来越受到科研工作者的广泛关注.而随着Factor等人于2011年提出有向图的(1,2)步竞争图的概念,并完全刻画了竞赛图的(1,2)步竞争图后,关于类竞赛图的(i,j)步竞争图问题也成为学者们研究的热点之一. 本文研究二部竞赛图的竞争图及其与(1,2)步竞争图之间的关系,并在竞赛图的(1,2)步竞争图的基础上,刻画了超竞赛图的(1,2)步竞争图. 本文共分为四章. 第一章,绪论.介绍了应用背景,研究现状和基本概念,并提出本文主要内容. 第二章,针对两个部集分别具有m和n个顶点的二部竞赛图,研究了它的竞争图的独立数,得出最大独立数αmax(m,n)和最小独立数αmin(m,n),通过证明得到如下结论: 1.αmax(m,n)={4,m=n=2;max{m,n}+1,其它. 2.αmin(m,n)={2,m=1,n任意,或者n=1,m任意;2,m=5,n≥10,或者n=5,m≥10;2,m≥6且n≥6;3,其它. 3.若m,n满足(m,n)≠(1,1),则对任意整数k∈{3,4,…,max{m,n}+1},总存在某个二部竞赛图H=(X,Y),满足|X|=m,|Y|=n,使得H的竞争图G的独立数α(G)=k. 第三章,研究了二部竞赛图的竞争图与(1,2)步竞争图的边集关系,得到这两个图的边数之差的下界ε1,2min(m,n)和上界ε1,2max(m,n),并举例说明了上下界的紧性,通过证明得到如下结论: 1.设m≥2,n≥2是正整数,则ε1,2min(m,n)=0.此外,若H∈H(m,n)满足ε1,2(H)=ε1,2min(m,n)=0当且仅当H是下面情形之一: (a)X→Y或Y→X; (b)H是一个4圈. 2.设m≥4,n≥4是正整数,则ε1,2max(m,n)=mn.且若H∈H(m,n)满足ε1,2(H)=ε1,2max(m,n)=mn当且仅当H的每个顶点的出度不小于2. 第四章,刻画了超竞赛图的(1,2)步竞争图,并且将一些结论推广到超竞赛图的(i,j)步竞争图,通过证明得到了: 1.设3≤k≤n-1,顶点数为n的图G是某个强连通k超竞赛图T的(1,2)步竞争图当且仅当G为Kn;Kn-E(P2),或者Kn-E(P3). 2.设3≤k≤n-1,顶点数为n的图G是某个k超竞赛图T的(1,2)步竞争图当且仅当G为Kn,Kn-1∪K1,Kn-E(P2),或者Kn-E(P3). 3.设T是一个顶点数为n的k超竞赛图,满足3≤k≤n-1.设i≥1,j≥2是整数,则Ci,j(T)=C1,2(T).