弧著色二部競賽圖的彩虹路的核

李瑞娟,曹艷琴

(山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,山西 太原 030006)

0 引言

本文中的有向圖是無環(huán)、無平行弧的簡單有向圖。路、跡和圈指的是有向路,有向跡和有向圈。本文中的術(shù)語可參看文獻(xiàn)[1]。

設(shè)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誘導(dǎo)的子圖指的是以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ǎo)出子圖都有核,則稱D是核完美有向圖。

一個有向圖D的弧著色指的是一個映射C∶A(D)→N,C(x,y)=i表示弧(x,y)著顏色i.如果D有一個弧著色,則稱D是弧著色有向圖,它的所有弧的顏色構(gòu)成的集合記為C(D).若C(D)=m,稱D為m-弧著色有向圖。如果弧著色有向圖D中所有弧的顏色都不同,稱D是彩虹圖。設(shè)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中所有弧的顏色構(gòu)成的集合記為C(P),C(vi,P,vj)表示P中從vi到vj的有向路中所有弧的顏色的集合。設(shè)C=v0v1…vkv0是弧著色有向圖D中的一個有向圈。圈C的長度記為l(C)=|V(C)|=k+1.如果C中所有弧的顏色都不同,則稱C是彩虹圈。設(shè)S?V(D)是一個非空子集滿足:(1)S中任意兩點之間在D中都沒有彩虹路;(2)對于任意的z∈V(D)-S,D中都有從z到S的彩虹路,則稱S是弧著色有向圖D的彩虹路的核。

設(shè)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等在文獻(xiàn)[2]中提出了單色路的核的概念,并且還證明了在每個2-弧著色的有向圖D中都有單色路的核。1988年,Shen在文獻(xiàn)[3]中證明了在m-弧著色的競賽圖中,如果所有3階子競賽圖滿足至多有一條弧與其他弧的顏色不同,其余弧的顏色都相同(稱為擬單色的),則T存在單色路的核。1996年,Galeana-Snchez在文獻(xiàn)[4]中證明了在m-弧著色的競賽圖T中,如果每個長至多為4的圈都是擬單色的,則T存在單色路的核。2004年,Galeana-Snchez和Rojas-Monroy在文獻(xiàn)[5]中證明了在弧著色的二部競賽圖D中,如果每個長為4的圈都是單色的,則D存在單色路的核。2009年,Galeana-Snchez和Rojas-Monroy在文獻(xiàn)[6]中證明了在弧著色的二部競賽圖D中,如果每個長為4的圈和每個階為4的傳遞子二部競賽圖T4都是擬單色的,則D存在單色路的核。2015年,Contreras-Balbuena,Galeana-Snchez和Rojas-Monro在文獻(xiàn)[7]中證明了弧著色有向圖D(可能有無窮多個點)中,如果每個有向圈和每個無限長的外向路中存在兩個連續(xù)的點xi和xi+1滿足弧著色有向圖D中有(xi,xi+1)單色路,則D中有單色路的核。2016年,Galeana-Snchez和Snchez-López在文獻(xiàn)[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中存在單色路的核，更多單色路的核的結(jié)論見參考文獻(xiàn)[9-13]。

2009年，Delgado-Escalante和Galeana-Snchez在文獻(xiàn)[14]中提出了正常著色路的核的概念。2018年,Bai等在文獻(xiàn)[15]中提出了如果一個弧著色有向圖D的所有圈都是正常著色的,則D中有正常著色路的核的猜想,他們證明了這一猜想在弧著色的無圈有向圖,半完全有向圖和二部競賽圖中的正確性。特別地,他們定義了弧著色有向圖中彩虹路的核,并證明了對于一個給定的弧著色有向圖,判斷是否存在彩虹路的核是NP-Hard問題。2018年,Delgado-Escalante和Galeana-Snchez在文獻(xiàn)[16]中給出了在弧著色的競賽圖、準(zhǔn)傳遞有向圖和k-部競賽圖中存在正常著色路的核的充分條件。2018年，Bai,Li和Zhang在文獻(xiàn)[17]中給出了弧著色競賽圖有彩虹路的核的充分條件。本文研究弧著色二部競賽圖中彩虹路的核的存在性,給出了弧著色二部競賽圖中存在彩虹路的核的充分條件。為了證明主要結(jié)論,我們將用到下面關(guān)于核完美有向圖的結(jié)論。

定理1[18]設(shè)D是一個有向圖,如果D中每個有向圈都至少有一條對稱弧,則D是核完美有向圖。

1 主要結(jié)論

引理1[4]設(shè)H=(V1,V2)是二部競賽圖,C=(v0,v1,…,vn)是H中的有向途徑。對于任意的i,j∈{0,1,2,…,n},如果vi與vj相鄰,當(dāng)且僅當(dāng)j-i≡1(mod 2).

引理2 設(shè)H=(V1,V2)是二部競賽圖,則H中每個長至多為6的有向閉途徑是一個有向圈,每個長至多為3的有向跡是一條有向路。

證明設(shè)C是H中的有向閉途徑,且l(C)≤6.因為H是二部競賽圖,所以l(C)≠2.若l(C)=4,設(shè)C=u0u1u2u3u0.因為(u0,u1)∈A(H),(u1,u2)∈A(H),且H是二部競賽圖,所以u0≠u2.同理u1≠u3.因此C是H中的有向圈。若l(C)=6,設(shè)C=u0u1u2u3u4u5u0.由于H=(V1,V2)是二部競賽圖,所以對于任意的i∈{0,2,4},j∈{1,3,5},有ui≠uj.又因為{(ui,ui+1),(ui+1,ui+2)}?A(H)(下標(biāo)mod 6),所以對于任意的i∈{0,1,…,5},ui≠ui+2,因此C是H中的有向圈。

設(shè)T是H中的有向跡,且l(T)≤3.若l(T)=1,結(jié)論顯然成立。若l(T)=2.設(shè)T=(u0,u1,u2),由于H是二部競賽圖,所以u0≠u2,則T是H中的有向路。若l(T)=3,設(shè)T=(u0,u1,u2,u3),同理由于H是二部競賽圖,因此對于任意的i∈{0,2},j∈{1,3},ui≠uj,即T是H中的有向路。

引理3 設(shè)H=(V1,V2)是m-弧著色的二部競賽圖,若H中的每個圈都是彩虹圈且每個子二部競賽圖TB4和CB5都是彩虹的,對于任意的u,v∈V(H),H中有彩虹(u,v)路但沒有彩虹(v,u)路,則下列結(jié)論至少有一個成立:

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

(2)H中存在長為2的(u,v)有向路。

證明設(shè)P是H中的彩虹(u,v)路,對P的長度l(P)作數(shù)學(xué)歸納。當(dāng)l(P)=1時,即(u,v)∈A(H).當(dāng)l(P)=2時,即H中存在長為2的彩虹(u,v)路,結(jié)論顯然成立。

假設(shè)當(dāng)l(P)=n時,結(jié)論成立。當(dāng)l(P)=n+1≥3時,設(shè)H中的彩虹(u,v)路為P=(u=u0,u1,…,un+1=v).當(dāng)n+1為奇數(shù)時,由引理1可知,un+1與u0相鄰。事實上,(u0,un+1)∈A(H).因為如果(un+1,u0)∈A(H),則(un+1,u0)是H中的彩虹(v,u)路,矛盾。因此,只需考慮當(dāng)n+1為偶數(shù)時,H中有長為2的(u,v)有向路。

當(dāng)n+1=4時,設(shè)P=(u=u0,u1,u2,u3,u4=v)是H中的彩虹(u,v)路,若(u0,u3)∈A(H),則(u=u0,u3,u4=v)是H中長為2的(u,v)有向路,結(jié)論成立。若(u1,u4)∈A(H),則(u=u0,u1,u4=v)是H中長為2的(u,v)有向路,結(jié)論成立。若(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)路,矛盾。

當(dāng)n+1=6時,設(shè)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)有向路,結(jié)論成立。若(u1,u6)∈A(H),則(u=u0,u1,u6=v)是H中長為2的(u,v)有向路,結(jié)論成立。故假設(shè)(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)路,矛盾。因此設(shè)C(u5,u0)=C(u6,u1)=α.顯然α?C(P),因為若α∈C(P),則u0Pu5u0和u1Pu6u1中至少有一個不是彩虹圈,矛盾。當(dāng)(u3,u6)∈A(H)時,若(u0,u3)∈A(H),則(u=u0,u3,u6=v)是H中長為2的(u,v)有向路,結(jié)論成立;若(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)路,矛盾。當(dāng)(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)路,矛盾。

當(dāng)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)有向路,結(jié)論成立。若(u1,un+1)∈A(H),則(u=u0,u1,un+1=v)是H中長為2的(u,v)有向路,結(jié)論成立。因此假設(shè)(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′)

當(dāng)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 設(shè)H=(V1,V2)是m-弧著色的二部競賽圖,若H中的每個圈都是彩虹圈且每個TB4和CB5都是彩虹的,則c(H)是核完美有向圖。

證明反證法。假設(shè)c(H)不是核完美有向圖,由定理1可設(shè)C=u0u1…unu0是c(H)中沒有對稱弧的圈。

斷言3 對于任意的i∈{0,1,…,n},或者(ui,ui+1)∈A(H),或者H中有長為2的(ui,ui+1)有向路。

證明 由假設(shè)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)有向路,結(jié)論成立。

下面對n進(jìn)行討論。

當(dāng)n=2時,即C=u0u1u2u0,由于H是二部競賽圖,所以存在i∈{0,1,2},使得(ui,ui+1)?A(H)(下標(biāo)mod 3).不妨設(shè)(u0,u1)?A(H),由斷言3,H中存在長為2的(u0,u1)有向路,不妨設(shè)為(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)有向路,不妨設(shè)為(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)有向路,不妨設(shè)為(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)有向路,不妨設(shè)為(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)中沒有對稱弧的圈矛盾。

當(dāng)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中的彩虹圈。

當(dāng)φ(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)中沒有對稱弧的圈矛盾。

當(dāng)φ(2j0+1)≠z2j0+1時,由φ的定義,φ(2j0+1)=z2j0=φ(2j0).由C′的構(gòu)造可得,φ(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 設(shè)H=(V1,V2)是m-弧著色的二部競賽圖,若H中的每個圈都是彩虹圈且每個TB4和CB5都是彩虹的,則H中有彩虹路的核。

證明由定理2可知,c(H)是核完美有向圖,設(shè)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的彩虹路的核。