弧着色二部竞赛图的彩虹路的核

李瑞娟,曹艳琴

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

0 引言

本文中的有向图是无环、无平行弧的简单有向图。路、迹和圈指的是有向路,有向迹和有向圈。本文中的术语可参看文献[1]。

设D是一个有向图,用V(D)和A(D)分别表示D的顶点集和弧集。对于任意的顶点x,y,z∈V(D),如果x,y间有弧,则称x,y相邻。如果(x,y)∈A(D)且(y,x)∈A(D),则称弧(x,y)是对称的,反之称为非对称的。对于一个非空顶点子集S⊆V(D),D的由S诱导的子图指的是以S为顶点集,以A(D)中两个端点都在S中的弧为弧集的有向图,记为D[S].如果S满足:(1)S中任意两点在D中都不相邻;(2)对于任意的z∈V(D)-S,存在一点v∈S,使得(z,v)∈A(D),则称S是有向图D的核。如果一个有向图D的任何导出子图都有核,则称D是核完美有向图。

一个有向图D的弧着色指的是一个映射C∶A(D)→N,C(x,y)=i表示弧(x,y)着颜色i.如果D有一个弧着色,则称D是弧着色有向图,它的所有弧的颜色构成的集合记为C(D).若C(D)=m,称D为m-弧着色有向图。如果弧着色有向图D中所有弧的颜色都不同,称D是彩虹图。设P=(v0,v1,…,vk)是弧着色有向图D中的一条(v0,vk)有向路。P的长度记为l(P)=|V(P)|-1=k.对于i,j∈{1,2,…,k},P中从vi到vj的有向路记为(vi,P,vj).如果P中所有弧的颜色都不同,称P是彩虹(v0,vk)路。P中所有弧的颜色构成的集合记为C(P),C(vi,P,vj)表示P中从vi到vj的有向路中所有弧的颜色的集合。设C=v0v1…vkv0是弧着色有向图D中的一个有向圈。圈C的长度记为l(C)=|V(C)|=k+1.如果C中所有弧的颜色都不同,则称C是彩虹圈。设S⊆V(D)是一个非空子集满足:(1)S中任意两点之间在D中都没有彩虹路;(2)对于任意的z∈V(D)-S,D中都有从z到S的彩虹路,则称S是弧着色有向图D的彩虹路的核。

设D是一个m-弧着色有向图,D的闭包c(D)是一个有向图满足:

V(c(D))=V(D),

A(c(D))=A(D)∪{(u,v)|D中有彩虹(u,v)路P}.

显然,c(D)的一个核是D的一个彩虹路的核。如图1是一个6个顶点的5-弧着色的二部竞赛图和它的闭包。

Fig.1 A 5-arc-coloured bipartite tournament on 6 vertices and its closure图1 6个顶点的5-弧着色二部竞赛图和它的闭包

如果一个有向图D的顶点集V(D)可以划分成两个非空的子集V1和V2,使得A(D)中的每条弧的两个端点分别在V1和V2中,则称D是二部有向图。如果V1中的每个顶点都与V2中的每个顶点相邻,称D为二部竞赛图。显然二部竞赛图不含有奇圈。如果4个顶点的二部竞赛图满足它的顶点集为{u,v,w,x},弧集为{(u,v),(v,w),(w,x),(u,x)},则将这样的二部竞赛图记为TB4.如果5个顶点二部竞赛图满足它的顶点集为{u,v,w,x,y},弧集为{(u,v),(v,w),(w,x),(x,y),(x,u),(y,v)},则将这样的二部竞赛图记为CB5.

1982年,Sands等在文献[2]中提出了单色路的核的概念,并且还证明了在每个2-弧着色的有向图D中都有单色路的核。1988年,Shen在文献[3]中证明了在m-弧着色的竞赛图中,如果所有3阶子竞赛图满足至多有一条弧与其他弧的颜色不同,其余弧的颜色都相同(称为拟单色的),则T存在单色路的核。1996年,Galeana-Snchez在文献[4]中证明了在m-弧着色的竞赛图T中,如果每个长至多为4的圈都是拟单色的,则T存在单色路的核。2004年,Galeana-Snchez和Rojas-Monroy在文献[5]中证明了在弧着色的二部竞赛图D中,如果每个长为4的圈都是单色的,则D存在单色路的核。2009年,Galeana-Snchez和Rojas-Monroy在文献[6]中证明了在弧着色的二部竞赛图D中,如果每个长为4的圈和每个阶为4的传递子二部竞赛图T4都是拟单色的,则D存在单色路的核。2015年,Contreras-Balbuena,Galeana-Snchez和Rojas-Monro在文献[7]中证明了弧着色有向图D(可能有无穷多个点)中,如果每个有向圈和每个无限长的外向路中存在两个连续的点xi和xi+1满足弧着色有向图D中有(xi,xi+1)单色路,则D中有单色路的核。2016年,Galeana-Snchez和Snchez-López在文献[8]中证明了对于一个弧着色有向图D和它的单色路的闭包c(D),如果c(D)的顶点集存在一个划分{V1,V2,…,Vp}满足:(1)对于任意的i,c(D)[Vi]是单色的;(2)任意的i≠j,如果(Vi,Vj)中有一条弧是c(D)的弧,则(Vi,Vj)⊆A(c(D)),那么D中存在单色路的核，更多单色路的核的结论见参考文献[9-13]。

2009年，Delgado-Escalante和Galeana-Snchez在文献[14]中提出了正常着色路的核的概念。2018年,Bai等在文献[15]中提出了如果一个弧着色有向图D的所有圈都是正常着色的,则D中有正常着色路的核的猜想,他们证明了这一猜想在弧着色的无圈有向图,半完全有向图和二部竞赛图中的正确性。特别地,他们定义了弧着色有向图中彩虹路的核,并证明了对于一个给定的弧着色有向图,判断是否存在彩虹路的核是NP-Hard问题。2018年,Delgado-Escalante和Galeana-Snchez在文献[16]中给出了在弧着色的竞赛图、准传递有向图和k-部竞赛图中存在正常着色路的核的充分条件。2018年，Bai,Li和Zhang在文献[17]中给出了弧着色竞赛图有彩虹路的核的充分条件。本文研究弧着色二部竞赛图中彩虹路的核的存在性,给出了弧着色二部竞赛图中存在彩虹路的核的充分条件。为了证明主要结论,我们将用到下面关于核完美有向图的结论。

定理1[18]设D是一个有向图,如果D中每个有向圈都至少有一条对称弧,则D是核完美有向图。

1 主要结论

引理1[4]设H=(V1,V2)是二部竞赛图,C=(v0,v1,…,vn)是H中的有向途径。对于任意的i,j∈{0,1,2,…,n},如果vi与vj相邻,当且仅当j-i≡1(mod 2).

引理2 设H=(V1,V2)是二部竞赛图,则H中每个长至多为6的有向闭途径是一个有向圈,每个长至多为3的有向迹是一条有向路。

证明设C是H中的有向闭途径,且l(C)≤6.因为H是二部竞赛图,所以l(C)≠2.若l(C)=4,设C=u0u1u2u3u0.因为(u0,u1)∈A(H),(u1,u2)∈A(H),且H是二部竞赛图,所以u0≠u2.同理u1≠u3.因此C是H中的有向圈。若l(C)=6,设C=u0u1u2u3u4u5u0.由于H=(V1,V2)是二部竞赛图,所以对于任意的i∈{0,2,4},j∈{1,3,5},有ui≠uj.又因为{(ui,ui+1),(ui+1,ui+2)}⊆A(H)(下标mod 6),所以对于任意的i∈{0,1,…,5},ui≠ui+2,因此C是H中的有向圈。

设T是H中的有向迹,且l(T)≤3.若l(T)=1,结论显然成立。若l(T)=2.设T=(u0,u1,u2),由于H是二部竞赛图,所以u0≠u2,则T是H中的有向路。若l(T)=3,设T=(u0,u1,u2,u3),同理由于H是二部竞赛图,因此对于任意的i∈{0,2},j∈{1,3},ui≠uj,即T是H中的有向路。

引理3 设H=(V1,V2)是m-弧着色的二部竞赛图,若H中的每个圈都是彩虹圈且每个子二部竞赛图TB4和CB5都是彩虹的,对于任意的u,v∈V(H),H中有彩虹(u,v)路但没有彩虹(v,u)路,则下列结论至少有一个成立:

(1)(u,v)∈A(H);

(2)H中存在长为2的(u,v)有向路。

证明设P是H中的彩虹(u,v)路,对P的长度l(P)作数学归纳。当l(P)=1时,即(u,v)∈A(H).当l(P)=2时,即H中存在长为2的彩虹(u,v)路,结论显然成立。

假设当l(P)=n时,结论成立。当l(P)=n+1≥3时,设H中的彩虹(u,v)路为P=(u=u0,u1,…,un+1=v).当n+1为奇数时,由引理1可知,un+1与u0相邻。事实上,(u0,un+1)∈A(H).因为如果(un+1,u0)∈A(H),则(un+1,u0)是H中的彩虹(v,u)路,矛盾。因此,只需考虑当n+1为偶数时,H中有长为2的(u,v)有向路。

当n+1=4时,设P=(u=u0,u1,u2,u3,u4=v)是H中的彩虹(u,v)路,若(u0,u3)∈A(H),则(u=u0,u3,u4=v)是H中长为2的(u,v)有向路,结论成立。若(u1,u4)∈A(H),则(u=u0,u1,u4=v)是H中长为2的(u,v)有向路,结论成立。若(u3,u0)∈A(H)且(u4,u1)∈A(H),则H[u0,u1,u2,u3,u4]是H中的CB5,又因为H中的CB5都是彩虹的,所以(v=u4,u1,u2,u3,u0=u)是H中的彩虹(v,u)路,矛盾。

当n+1=6时,设P=(u=u0,u1,u2,u3,u4,u5,u6=v)是H中的彩虹(u,v)路。若(u0,u5)∈A(H),则(u=u0,u5,u6=v)是H中长为2的(u,v)有向路,结论成立。若(u1,u6)∈A(H),则(u=u0,u1,u6=v)是H中长为2的(u,v)有向路,结论成立。故假设(u5,u0)∈A(H)且(u6,u1)∈A(H),因为u0Pu5u0是H中的彩虹圈,所以C(u5,u0)∉C(u1,P,u5).同理因为u1Pu6u1是彩虹圈,所以C(u6,u1)∉C(u1,P,u5).若C(u5,u0)≠C(u6,u1),则(v=u6,u1,P,u5,u0=u)是H中的彩虹(v,u)路,矛盾。因此设C(u5,u0)=C(u6,u1)=α.显然α∉C(P),因为若α∈C(P),则u0Pu5u0和u1Pu6u1中至少有一个不是彩虹圈,矛盾。当(u3,u6)∈A(H)时,若(u0,u3)∈A(H),则(u=u0,u3,u6=v)是H中长为2的(u,v)有向路,结论成立;若(u3,u0)∈A(H),则u0u1u2u3u0是H中的有向圈且H[u3,u4,u5,u0]是H中的TB4,由引理3的条件可知,C(u3,u0)∉{C(u1,P,u3)∪α},因此(v=u6,u1,u2,u3,u0=u)是H中的彩虹(v,u)路,矛盾。当(u6,u3)∈A(H)时,由于u3u4u5u6u3是H中的圈且H[u1,u2,u3,u6]是TB4,由引理3的条件可知,C(u6,u3)∉{C(u3,P,u5)∪α},因此(v=u6,u3,u4,u5,u0=u)是H中的彩虹(v,u)路,矛盾。

当n+1≥8时,因为n≡1(mod 2),由引理1可知,u0与un相邻,u1与un+1相邻。若(u0,un)∈A(H),则(u=u0,un,un+1=v)是H中长为2的(u,v)有向路,结论成立。若(u1,un+1)∈A(H),则(u=u0,u1,un+1=v)是H中长为2的(u,v)有向路,结论成立。因此假设(un,u0)∈A(H)且(un+1,u1)∈A(H).因为u0Punu0是彩虹圈,所以C(un,u0)∉C(u1,P,un).同理因为u1Pun+1u1是彩虹圈,所以C(un+1,u1)∉C(u1,P,un).若C(un,u0)≠C(un+1,u1),则(v=un+1,u1,P,un,u0=u)是H中的彩虹(v,u)路,矛盾。因此考虑C(un,u0)=C(un+1,u1)=α的情形。显然α∉C(P),因为若α∈C(P),则u0Punu0和u1Pun+1u1中至少有一个不是彩虹圈,矛盾。

断言1 若存在i,j∈{1,2,…,n},j-i≥3,使得(ui,uj)∈A(H),则H中有长为2的(u,v)有向路。

证明 由定理的条件,u0PuiujPunu0和u1PuiujPun+1u1是H中的彩虹圈,所以C(ui,uj)∉C(u0,P,ui)∪C(uj,P,un+1),则P′=(u=u0,P,ui,uj,P,un,un+1=v)是H中的彩虹(u,v)路,且l(P′)

当i=1时,即(un+1,u3)∈A(H),又因为(un+1,u1)∈A(H),所以H[un+1,u1,u2,u3]是H中的TB4,又因为H中的TB4是彩虹的,所以C(un+1,u3)≠C(un+1,u1)=α.又u3Pun+1u3是H中彩虹圈,所以C(un+1,u3)∉C(u3,P,un),即(v=un+1,u3,P,un,u0=u)是H中的彩虹(v,u)路,矛盾。

定理2 设H=(V1,V2)是m-弧着色的二部竞赛图,若H中的每个圈都是彩虹圈且每个TB4和CB5都是彩虹的,则c(H)是核完美有向图。

证明反证法。假设c(H)不是核完美有向图,由定理1可设C=u0u1…unu0是c(H)中没有对称弧的圈。

断言3 对于任意的i∈{0,1,…,n},或者(ui,ui+1)∈A(H),或者H中有长为2的(ui,ui+1)有向路。

证明 由假设C是c(H)中没有对称弧的圈,所以对于任意的i∈{0,1,2,…,n},有(ui,ui+1)∈A(c(H))且(ui+1,ui)∉A(c(H)),由c(H)的定义可知,对于任意的i∈{0,1,2,…,n},H中有彩虹(ui,ui+1)路且没有彩虹(ui+1,ui)路,由引理2可知,或者(ui,ui+1)∈A(H),或者H中有长为2的(ui,ui+1)有向路,结论成立。

下面对n进行讨论。

当n=2时,即C=u0u1u2u0,由于H是二部竞赛图,所以存在i∈{0,1,2},使得(ui,ui+1)∉A(H)(下标mod 3).不妨设(u0,u1)∉A(H),由断言3,H中存在长为2的(u0,u1)有向路,不妨设为(u0,v0,u1)。

若{(u1,u2),(u2,u0)}⊆A(H),由定理2的条件可知,u0v0u1u2u0是H中的彩虹圈,则(u1,u2,u0)是H中的彩虹(u1,u0)路。由c(H)的定义可得,(u1,u0)∈A(c(H))是C中弧(u0,u1)的对称弧,与C是c(H)中没有对称弧的圈矛盾。

若(u1,u2)∈A(H),(u2,u0)∉A(H),由断言3,H中存在长为2的(u2,u0)有向路,不妨设为(u2,v2,u0),则C′=u0v0u1u2v2u0是H中一个长为5的闭途径,由引理2可知,C′是H中的一个长为5的圈,与H是二部竞赛图矛盾。同理若(u2,u0)∈A(H),(u1,u2)∉A(H),由断言3,H中存在长为2的(u1,u2)有向路,不妨设为(u1,v1,u2),则C′=u0v0u1v1u2u0是H中一个长为5的闭途径,由引理2可知,C′是H中的一个长为5的圈,与H是二部竞赛图矛盾。

若(u1,u2)∉A(H)且(u2,u0)∉A(H),由断言3,对于任意的i∈{0,1,2},H中存在长为2的(ui,ui+1)有向路,不妨设为(ui,vi,ui+1),则C′=u0v0u1v1u2v2u0是H中的长为6的闭途径。由引理2和定理2的条件得,C′是H中的彩虹圈,因此(u1,v1,u2,v2,u0)是H中的彩虹(u1,u0)路。由c(H)的定义可得(u1,u0)∈A(c(H))是C中弧(u0,u1)的对称弧,与C是c(H)中没有对称弧的圈矛盾。

当n≥3时,由断言3可令

情形1 (z3,z0)∈A(H).由引理2和定理2的条件可知,z0z1z2z3z0是H中的彩虹圈,由C′的定义可知,u1=z1或u1=z2.若u1=z1,则(u1=z1,z2,z3,z0=u0)是H中的彩虹(u1,u0)路,所以(u1,u0)∈A(c(H))是C中弧(u0,u1)的对称弧,与C是c(H)中没有对称弧的圈矛盾。若u1=z2,则(u1=z2,z3,z0=u0)是H中的彩虹(u1,u0)路,所以(u1,u0)∈A(c(H))是C中弧(u0,u1)的对称弧,与C是c(H)中没有对称弧的圈矛盾。

情形2 (z0,zk-2)∈A(H).由引理2和定理2的条件可知,z0zk-2zk-1zkz0是H的彩虹圈,由C′的定义,un=zk-1或un=zk.若un=zk-1,则(u0=z0,zk-2,zk-1=un)是H中的彩虹(u0,un)路,由c(H)的定义,(u0,un)∈A(c(H))是C中弧(un,u0)的对称弧,与C是c(H)中无对称弧的圈矛盾。若un=zk,(u0=z0,zk-2,zk-1,zk=un)是H中的彩虹(u0,un)路,由c(H)的定义,(u0,un)∈A(c(H))是C中弧(un,u0)的对称弧,与C是c(H)中没有对称弧的圈矛盾。

则(z0,z2j0+1)∈A(H),(z2j0+3,z0)∈A(H),由定理2的条件,z0z2j0+1z2j0+2z2j0+3z0是H中的彩虹圈。

当φ(2j0+1)=z2j0+1时,令z2j0+1=uj.由C′的定义,uj+1=z2j0+2或uj+1=z2j0+3.若uj+1=z2j0+2,则(uj+1=z2j0+2,z2j0+3,z0,z2j0+1=uj)是H中的彩虹(uj+1,uj)路,由c(H)的定义,(uj+1,uj)∈A(c(H))是C中弧(uj,uj+1)的对称弧,与C是c(H)中没有对称弧的圈矛盾。若uj+1=z2j0+3,则(uj+1=z2j0+3,z0,z2j0+1=uj)是H中的彩虹(uj+1,uj)路,由c(H)的定义,(uj+1,uj)∈A(c(H))是C中弧(uj,uj+1)的对称弧,与C是c(H)中没有对称弧的圈矛盾。

当φ(2j0+1)≠z2j0+1时,由φ的定义,φ(2j0+1)=z2j0=φ(2j0).由C′的构造可得,φ(2j0+2)=z2j0+2,令z2j0+2=uj(2≤j≤n-1),则z2j0=uj-1.由于(2j0+3)-2j0≡1(mod 2),由引理1,z2j0与z2j0+3相邻。

若(z2j0+3,z2j0)∈A(H),由定理2的条件,z2j0z2j0+1z2j0+2z2j0+3z2j0是H中的彩虹圈,则(uj=z2j0+2,z2j0+3,z2j0=uj-1)是H中的彩虹(uj,uj-1)路,由c(H)的定义可知,(uj,uj-1)∈A(c(H))是C中弧(uj-1,uj)的对称弧,与C是c(H)中没有对称弧的圈矛盾。

若(z2j0,z2j0+3)∈A(H),由于2j0-1≡1(mod 2),由引理1,z0与z2j0-1相邻,由j0的极小性得,(z0,z2j0-1)∈A(H),由定理2的条件,则z0z2j0-1z2j0z2j0+1z2j0+2z2j0+3z0是H中的彩虹圈,所以(uj=z2j0+2,z2j0+3,z0,z2j0-1,z2j0=uj-1)是H中的彩虹(uj,uj-1)路,由c(H)的定义,(uj,uj-1)∈A(c(H))是C中弧(uj-1,uj)的对称弧,与C是c(H)中没有对称弧的圈矛盾。

综上所述,在每一种情形下都找到了矛盾,因此c(H)是核完美有向图。

定理3 设H=(V1,V2)是m-弧着色的二部竞赛图,若H中的每个圈都是彩虹圈且每个TB4和CB5都是彩虹的,则H中有彩虹路的核。

证明由定理2可知,c(H)是核完美有向图,设S⊆V(c(H))是c(H)的一个核,因此对于任意的x,y∈S,x和y在c(H)中不相邻且对任意的z∈V(c(H))-S,存在一点v∈S,使得(z,v)∈A(c(H)).由c(H)的定义,对任意的x,y∈S,H中没有彩虹(x,y)路且对任意的z∈V(H)-S,H中有从z到S的彩虹路。因此S是H的彩虹路的核。