二部竞赛图的竞争图与(1,2)步竞争图的边集关系*

李瑞娟， 安晓婷

(山西大学 数学科学学院， 山西 太原 030006)

二部竞赛图的竞争图与(1,2)步竞争图的边集关系*

李瑞娟， 安晓婷

(山西大学 数学科学学院， 山西 太原 030006)

二部竞赛图； 竞争图； (1,2)步竞争图

0 引 言

本文中的无向图是无环、 无重边的简单无向图， 涉及到的有向图是无环、 无平行弧的简单有向图[1].

设G是一个无向图，V(G)和E(G)分别表示G的顶点集和边集. 假设H是G的一个子图， 满足V(H)=V(G)， 则称H是G的生成子图. 假设V′是V(G)的一个非空子集. 以V′为顶点集， 以两端点均在V′中的边的全体为边集所组成的子图， 称为G的诱导子图， 记为G[V′].

D中的一条(x,y)-有向途径是指一些弧与顶点的交错序列， 例如x， (x,v1)，v1， (v1,v2),v2,…，vk-1,(vk-1,vk),vk, (vk,y),y. 顶点x到y的距离是指最短(x,y)-途径的弧数， 记为dD(x,y). 有向图D-x是通过从D中删去顶点x和与x相关联的弧而获得的图.

无向图的定向图是指给无向图每一条边一个方向形成的有向图. 竞赛图是完全无向图的定向图， 即竞赛图的任意两个顶点之间有且仅有一条弧. 完全偶图是具有二分类(X,Y)的简单无向偶图， 它的顶点集分为两个非空子集X和Y， 其中X的每个顶点都与Y的每个顶点相连. 两个部集的顶点个数分别是m和n的完全偶图， 记作Km,n. 二部竞赛图是完全偶图的定向图. 换句话说， 设有向图H是一个二部竞赛图， 如果H的顶点集可分为两个非空子集X,Y， 使得X,Y内部的顶点之间没有弧， 且X上的每一个顶点与Y上的每一个顶点之间有且仅有一条弧， 则称X,Y是H的两个部集.

对于顶点x,y∈V(D)， 如果D中存在不同于x,y的顶点z， 使得x→z且y→z， 则称x和y是D中的竞争对. 有向图D=(V,A)的竞争图是一个无向图G， 它的顶点集V(G)是D的顶点集V(D)， 且xy是G的一条边当且仅当在D中x和y是竞争对， 记为C(D). 对于无向图G， 如果V(G)=V(D)， 并且xy∈E(G)当且仅当V(D)中存在顶点z≠x，y， 使得dD-y(x,z)=1，dD-x(y,z)≤2或者dD-x(y,z)=1，dD-y(x,z)≤2， 那么称G为D的(1,2)步竞争图， 记为C1,2(D). 图 1 是一个二部竞赛图及其竞争图和(1,2)步竞争图.

图 1 二部竞赛图H及其竞争图和(1,2)步竞争图Fig.1 A bipartite tournament H， its competition graph and (1,2)-step competition graph

显然，C(D)的边集是C1,2(D)的边集的子集， 我们将相差边集记为E1,2(D)， 即

E1,2(D)=E(C1,2(D))E(C(D)).

在下文中， 我们用ε1,2(D)表示|E1,2(D)|的值.

竞争图的概念是由美国生物学家Cohen在研究食物链网络模型时提出的. 除生态学这一应用外， 竞争图的概念还被应用在噪声信道下通信的研究和设定收音机或电视发射机频道等方面[2,3]. 2011年， 随着对竞争图的研究深入， Factor等提出了有向图的(1,2)步竞争图的概念， 并完全刻画了竞赛图的(1,2)步竞争图[4]. 近年来， 人们还研究某些特殊有向图的(1,2)步竞争图和(i,k)步竞争图等[5-8]. 2016年， Kim等[9]研究了二部竞赛图的竞争图， 并用边团覆盖等参数刻画了二部竞赛图的竞争图. 因此， 二部竞赛图的(1,2)步竞争图也是一个值得研究的课题. 本文主要研究二部竞赛图H的竞争图与(1,2)步竞争图的边集关系. 下面是与本文相关的一些简单结论.

命题1[9]设D是一个具有二分类(U,V)的完全偶图Km,n的定向图， 其中|U|=m， |V|=n. 则C(D)没有U中顶点和V中顶点之间的边.

命题2 设H=(X,Y)是一个二部竞赛图， 则C(H)是C1,2(H)的一个生成子图， 且

i)X在C(H)和在C1,2(H)上的诱导子图同构，Y在C(H)和在C1,2(H) 上的诱导子图也同构;

ii) ∀x∈X，y∈Y，xy不是C(H)的边. 即若xy∈E1,2(H)(E1,2(H)=E(C1,2(H))E(C(H)))， 则必有x和y属于不同部集.

证明显然，C(H)是C1,2(H)的子图. 又V(C(H))=V(H)=V(C1,2(H))， 故C(H)是C1,2(H) 的生成子图. 设X在C(H)和在C1,2(H)上的诱导子图分别为G1和G2. 由于C(H)是C1,2(H)的子图， 故E(G1)⊆E(G2). 设i,j∈V(X)， 若ij∈E(G2)， 则ij∈C1,2(H). 故存在顶点k≠i，j使得dH-j(i,k)=1，dH-i(j,k)≤2或者dH-i(j,k)=1，dH-j(i,k)≤2. 由于i，j属于同一部集， 故只能dH-i(j,k)=1，dH-j(i,k)=1， 即N+(i)∩N+(j)≠Ø. 故ij∈E(G1)， 即E(G2)⊆E(G1). 因此，E(G1)=E(G2). 又V(G1)=V(X)=V(G2)， 则X在C(H)和在C1,2(H)上的诱导子图同构. 同理，Y在C(H)和在C1,2(H) 上的诱导子图也同构.

根据命题1和(1,2)步竞争图的定义， 结论ii)显然成立.

1 二部竞赛图的竞争图与(1,2)步竞争图的边数关系

设m,n是两个正整数. H(m,n)是一个二部竞赛图的集合， 满足H∈H(m,n)当且仅当H=(X,Y)是某个二部竞赛图， 使得|X|=m， |Y|=n. 因ε1,2(H)表示H的(1,2)步竞争图C1,2(H) 与竞争图C(H)的边集之差， 在下文中， 记

为了方便讨论， 我们设m≤n.

对m=1， 根据有向图的(1,2)步竞争图和二部竞赛图的定义， 显然有下面的结论.

i)X→Y或Y→X;

ii)H是一个4圈.

情形1 存在顶点xi,xj∈X，yα∈Y， 使得xi→yα且yα→xj.

若yγ→xi或yγ→xj， 则dH-xj(yγ,xi)=1，dH-yγ(xj,xi)=2 或者dH-xi(yγ,xj)=1，dH-yγ(xi,xj)=2. 因此，xjyγ∈E(C1,2(H)) 或者xiyγ∈E(C1,2(H))， 即xjyγ∈E1,2(H)或者xiyγ∈E1,2(H)， 与假设矛盾.

情形2 存在顶点xi,xj∈X，yα,yβ∈Y， 使得xi→yα且yβ→xj.

显然， 在这种情形下，H不是一个4圈. 现在考虑xj与yα之间的控制关系. 若xj→yα， 则dH-yβ(xi,yα)=1，dH-xi(yβ,yα)=2， 即xiyβ∈E(C1,2(H))， 与假设矛盾. 若yα→xj， 则dH-xi(yβ,xj)=1，dH-yβ(xi,xj)=2， 即xiyβ∈E(C1,2(H))， 与假设矛盾.

因此， 定理成立.

V(H)=X∪Y=

{x1,x2,…,xm}∪{y1,y2,…,yn}，

A(H)={(xi,y1)(xi,y2)(yj,xi)|1≤i≤2，

3≤j≤n}∪{(y1,xk)(y2,xk)(xk,yl)|

3≤k≤m, 3≤l≤n}.

设xi∈X，yk∈Y. 由于H的每个顶点的出度不小于2， 故存在不同于yk的顶点yl， 使得xi→yl. 同理， 存在顶点xj， 使得yk→xj. 此时， 不论xj和yl之间的控制关系如何， 都满足xiyk∈C1,2(H). 根据xi和yk的任意性， 可知X部中的每个顶点与Y部中的每个顶点在C1,2(H)中相邻.

因此， 定理成立.

注记由定理3的证明可知， 对所有正整数m，n， 如果二部竞赛图H∈H(m,n)， 那么ε1,2(H)=mn， 当且仅当H的每个顶点的出度不小于2.

证明构造二部竞赛图H如下：

V(H)=X∪Y={x1,x2}∪{y1,y2,…,yn}，

A(H)={(x1,y1),(x2,y1)}∪{(yi,xj)|

2≤i≤n, 1≤j≤2}.

根据(1,2)步竞争图的定义， 容易得出，xiyj∈E(C1,2(H)) (1≤i≤2， 2≤j≤n)， 这恰好是二部竞赛图H的(1,2)步竞争图与竞争图相差的边集. 因此，ε1,2(H)=2(n-1).

定理5 设n≥3是正整数， 则

证明1) 当n=3时， 构造二部竞赛图H如下：

V(H)=X∪Y={x1,x2,x3}∪{y1,y2,y3}，

A(H)={(xi,y1)， (yj,xk)|

1≤i≤3, 2≤j≤3, 1≤k≤3}.

容易得出，xiyj∈E(C1,2(H)) (1≤i≤3， 2≤j≤3)， 即xiyj∈E1,2(H). 而y1与xi(i=1,2,3)均不相邻. 故ε1,2(H)=6.

2) 当n=4时， 构造二部竞赛图H如下：

V(H)=X∪Y=

{x1,x2,x3}∪{y1,y2,y3,y4}，

A(H)={(x1,y1),(x1,y2),(y3,x1),(y4,

x1)}∪{(yi,xj),(xj,yk)|1≤i≤2,

2≤j≤3, 3≤k≤4}.

不难验证， 除x1y3和x1y4外，x1y1，x1y2和xiyj(2≤i≤3， 1≤j≤4)都在E(C1,2(H))中. 根据命题1， 它们不是C(H)的边. 因此，ε1,2(H)=10.

3) 当n=5时， 构造二部竞赛图H如下：

V(H)=X∪Y=

{x1,x2,x3}∪{y1,y2,…,y5}，

A(H)={(x1,y1)(x1,y2)(yi,x1)|

3≤i≤5}∪{(y1,x2)(y2,x2)(y5,x2)(x2,yj)|

3≤j≤4}∪{(x3,y4)(x3,y5)(yk,x3)|

1≤k≤3}.

不难验证， 除去x1y4外，xiyj(1≤i≤3， 1≤j≤5)都在E(C1,2(H))中， 但它们不是C(H)的边. 因此，ε1,2(H)=14.

4) 当n≥6时， 构造二部竞赛图H如下：

V(H)=X∪Y=

{x1,x2,x3}∪{y1,y2,…,yn}，

A(H)=

{(x1,y1)(x1,y2)(yi,x1)|3≤i≤n}∪

{(x2,y3)(x2,y4)(y1,x2)(y2,x2)(yj,x2)|

5≤j≤n}∪{(x3,yk)(yl,x3)|

5≤k≤n， 1≤l≤4}.

定理成立.

[1] Bang-Jensen J, Gutin G. Digraphs: theory, algorithms and applications[M]. London: Spring-Verlag, 2001.

[2] Wang J H, Tang Z, Xu X S, et al. A discrete competitive Hopfield neural network for cellular channel assignment problems[J]. Neurocomputing, 2005, 67(1): 436-442.

[3] Fraughnaugh K F, Lundgren J R, Merz S K, et al. Competition graphs of strongly connected and hamiltonian digraphs[J]. Siam Journal on Discrete Mathematics, 1995, 8(2): 179-185.

[4] Factor K A S, Merz S K. The (1,2)-step competition graph of a tournament[J]. Discrete Applied Mathematics, 2011, 159(2-3): 100-103.

[5] 张新鸿, 李瑞娟, 李胜家. 圆有向图的(i,k)步竞争图[J]. 应用数学学报, 2013, 36(6): 1037-1043.

Zhang Xinhong, Li Ruijuan, Li Shengjia. The (i,k)-step competition graph of a round digraph[J]. Acta Mathematicae Applicatae Sinica, 2013, 36(6): 1037-1043. (in Chinese)

[6] 张新鸿, 李瑞娟, 李胜家. 圆可分解的局部半完全有向图的(i,k)步竞争图[J]. 中北大学学报(自然科学版), 2013, 34(5): 488-492.

Zhang Xinhong, Li Ruijuan, Li Shengjia. The (i,k)-step competition graph of a round decomposable locally semicomplete digraph[J]. Journal of North University of China (Natural Science Edition), 2013, 34(5): 488-492. (in Chinese)

[7] Zhang X H, Li R J, Li S J, et al. A note on the existence of edges in the (1,2)-step competition graph of a round digraph[J]. Australasian Journal of Combinatorics, 2013, 57: 287-292.

[8] Zhang X H, Li R J. The (1,2)-step competition graph of a pure local tournament that is not round decomposable[J]. Discrete Applied Mathematics, 2016, 205: 180-190.

[9] Kim S R, Lee J Y, Park B, et al. The competition graphs of oriented complete bipartite graphs[J]. Discrete Applied Mathematics, 2016, 201: 182-190.

RelationoftheEdgeSetsBetweentheCompetitionGraphandthe(1,2)-stepCompetitionGraphofaBipartiteTournament

LI Rui-juan， AN Xiao-ting

(School of Mathematical Sciences， Shanxi University, Taiyuan 030006， China)

bipartite tournament; competition graph; (1,2)-step competition graph

1673-3193(2017)03-0264-05

2016-09-16

国家自然科学基金资助项目(11401353)； 山西省回国留学人员科研资助项目(2013-017)

李瑞娟(1980-)， 女， 副教授， 主要从事图论及其应用的研究.

O157.5

A

10.3969/j.issn.1673-3193.2017.03.003