正則有向圖中的不相交圈

程攀攀 何志紅

摘 要：2020年，Tan提出猜想：所有的三正則有向圖除D73，D83和D2n2外都包含兩個(gè)不同長(zhǎng)度且不相交的圈。Tan證明了圍長(zhǎng)為3和4的三正則有向圖對(duì)于這個(gè)猜想均成立。受此啟發(fā)，本文證明這個(gè)猜想對(duì)于圍長(zhǎng)為5且具有至少4個(gè)圈的圈因子的三正則有向圖也是成立的。

關(guān)鍵詞：三正則有向圖;圈因子;不交圈

中圖分類號(hào)：O157.6? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：1673-260X（2021）01-0001-03

1 引言與預(yù)備知識(shí)

設(shè)D=（V，A）為一有向圖，其中頂點(diǎn)集合為V（D）（或簡(jiǎn)寫(xiě)為V），弧集合為A（D）（或簡(jiǎn)寫(xiě)為A），除特別說(shuō)明外，本文中研究的有向圖均為有限簡(jiǎn)單有向圖（不包含多重弧和自環(huán)），關(guān)于有向圖用到的符號(hào)見(jiàn)參考文獻(xiàn)[1]。

對(duì)于有向圖D中的任意一個(gè)頂點(diǎn)v，定義如下集合

ND+（v）={u∈V-v：vu∈A}，

ND-（v）={w∈V-v：wv∈A}。

這里ND+（v）表示頂點(diǎn)v的出鄰集，ND-（v）表示頂點(diǎn)v的入鄰集，ND+（v）和ND-（v）中的頂點(diǎn)分別表示v的出鄰點(diǎn)和入鄰點(diǎn)。dD+（v）表示頂點(diǎn)v的出度，即v的出鄰點(diǎn)個(gè)數(shù)（dD+（v）=|ND+（v）|），ND-（v）表示頂點(diǎn)v的入度，即v的入鄰點(diǎn)的個(gè)數(shù)（ND-（v）=|ND-（v）|）。若對(duì)D中任意一個(gè)頂點(diǎn)v都有dD+（v）=dD-（v），則稱有向圖D為k正則有向圖。

本文中提到的圈（路）均為有向圈（路），不相交的圈指的是頂點(diǎn)不相交的圈，圍長(zhǎng)是指一個(gè)有向圖中最短圈的長(zhǎng)度。如果u∈V（C），則用u-和u+分別表示C上u的前趨和后繼，同樣的，u- -和u++分別表示C上u-的前趨和u+的后繼。若F=C1∪C2∪…∪Ct為有向圖D的生成有向子圖且C1，C2，…，Ct為兩兩不相交的圈，則稱F為有向圖D的一個(gè)圈因子。如果C=v0v1…vl-1v0是D中一個(gè)長(zhǎng)度為l的圈，并且vi，vj∈V（C），這時(shí)viCvj表示的是vi，vi+1，vi+2，…，vj（指標(biāo)模l）這個(gè)有序列。另外，根據(jù)文獻(xiàn)[2]得知有向圖D73，D83和D2n2（n≥2）的定義為：

D2n2=（V，A），其中V={xi，yi|i=0，1，…，n-1}，A={xiyi， yixi，xixi+1，xiyi+1，yixi+1，yiyi+1|i=0，1，…，n-1}（這里的指標(biāo)是模n的）;

D73=（V，A），其中A={vivj|（j-i）（mod7）∈{1，2，4}}，V={v0，v1，…，v6};

D83=（V，A），其中V={v0，v1，…，v5，t，w}，A=A1∪A2∪A3，這里A1={vi，vj|j-i=1 or 2（mod6）}，A2={tvi，viw|i=0，2，4}，A3={wvi，vit|i=1，3，5}。

Thomassen[3]和Lichiardopol[4]等研究了有向圖中不交圈的問(wèn)題，還有一些文獻(xiàn)[5-7]研究了競(jìng)賽圖中不交圈問(wèn)題，但是沒(méi)有考慮圈的長(zhǎng)度.在近幾年的研究中，許多研究者對(duì)有向圖中是否存在兩個(gè)長(zhǎng)度不同且不相交的圈問(wèn)題十分感興趣，Gao和Ma[8]證明了一類4-弧-控制有向圖包含兩個(gè)長(zhǎng)度不同且不相交的圈，下面我們?cè)俳榻B幾個(gè)相關(guān)的猜想和定理。

猜想1（Henning和Yeo[9]） 每一個(gè)三正則二部有向圖均包含兩個(gè)長(zhǎng)度不同且不相交的圈。

猜想2（Tan[2]） 所有的三正則有向圖除D73，D83和D2n2外都包含兩個(gè)長(zhǎng)度不同且不相交的圈。

定理1（Tan[10]） 每個(gè)具有至少兩個(gè)圈因子的三正則二部有向圖都包含兩個(gè)長(zhǎng)度不同且不相交的圈。

定理2（Tan[11]） 如果D是圍長(zhǎng)為3的三正則有向圖，則D不包含兩個(gè)長(zhǎng)度不同且不相交的圈當(dāng)且僅當(dāng)D和D73或D83同構(gòu)。

定理3（Tan[2]） 每一個(gè)圍長(zhǎng)為4的三正則有向圖都包含兩個(gè)長(zhǎng)度不同且不相交的圈。

對(duì)于猜想2，Tan[2，11]證明了三正則有向圖的圍長(zhǎng)為3和4時(shí)都是成立的。受Tan[10]的啟發(fā)，我們證明了每一個(gè)具有至少4個(gè)圈的圈因子的三正則有向圖當(dāng)圍長(zhǎng)為5時(shí)都包含兩個(gè)長(zhǎng)度不同且不相交的圈，即本文中的定理4。

2 主要結(jié)果

定理4 每一個(gè)圍長(zhǎng)為5且具有至少4個(gè)圈的圈因子的三正則有向圖D都包含兩個(gè)長(zhǎng)度不同且不相交的圈。

證明 設(shè)F=C0∪C1∪…∪Cl-1為D的一個(gè)圈因子且l≥4。因?yàn)镈的圍長(zhǎng)為5，所以|V（Ci）|≥5（i=0，1，2，…，l-1）。顯然，如果這些圈因子中，存在兩個(gè)圈的長(zhǎng)度不同或者存在一個(gè)圈Ci（0≤i≤l-1）內(nèi)部有弦，結(jié)論是成立的。由此，只需考慮圈因子中所有圈的長(zhǎng)度均相等且每個(gè)圈都是無(wú)弦時(shí)的情況，即 |V（C0）|=|V（C1）|=…=|V（Cl-1）|=k≥5。因?yàn)镈是三正則有向圖，所以圈Ci上的每個(gè)頂點(diǎn)都恰有兩個(gè)出鄰點(diǎn)和兩個(gè)入鄰點(diǎn)在V（D）＼V（Ci）（指標(biāo)模l）上。運(yùn)用反證法，假設(shè)定理4是錯(cuò)誤的，即其所有不交圈的長(zhǎng)度均相等。通過(guò)Tan[10]文章中的Claim 2可知D中所有的弧都是從Ci到Ci+1上的（這里的指標(biāo)都是模l的），且Henning和Yeo[9]文章中的Claim Ⅲ可知對(duì)于D中任意兩個(gè)頂點(diǎn)的集合{a1，a2}？哿V（C0）以及{d1，d2}？哿V（C3），在D＼[V（C1（∪V（C2）]上存在從{d1，d2}到{a1，a2}的兩條不相交的路。

我們?cè)贑1上任選一個(gè)點(diǎn)b1，設(shè)a1和a1為b1在V（C0）上的兩個(gè)入鄰點(diǎn)，c1為b1在V（C2）上的出鄰點(diǎn)，d1為c1在V（C3）上的出鄰點(diǎn)。設(shè)b1-為b1在V（C1）上的前趨，c1-為c1在V（C2）上的前趨。因?yàn)镈是三正則有向圖，所以c1-在V（C3）上的出鄰點(diǎn)至少有一個(gè)不同于d1，設(shè)為d2。此時(shí)，a1≠a2，d1≠d2，可知在? D＼[V（C1）∪V（C2）]上，從{d1，d2}到{a1，a2}存在兩條不相交的路，設(shè)為P1和P2。首先，假設(shè)P1表示從d1到a1的路，P2表示從d2到a2的路。由此，設(shè)a2在V（C1）上且不同于b1的出鄰點(diǎn)為b2。

（i）當(dāng)b2≠b1-時(shí)。

（a）若b2在V（C2）上的兩個(gè)出鄰點(diǎn)c2和c3均不同于c1，那么我們構(gòu)造3條路：

R1=a1，b1，c1，d1，R2=a2，b2，c2C2c1-，d2，R3=a2，b2，c3C2c1-，d2。令C1*=P1∪R1，C2*=P2∪R2，C3*=P2∪R3，可知|V（C2*）| ≠|(zhì)V（C3*）|，并且C3*和C3*均與C1*不相交，因此可找到兩個(gè)長(zhǎng)度不同且不相交的圈，與假設(shè)矛盾。

（b）若c1是b2在V（C2）上的一個(gè)出鄰點(diǎn)，那么b1-在V（C2）上的兩個(gè)出鄰點(diǎn)均不同于c1，設(shè)為c4和c5?？蓸?gòu)造下面3條路：R1=a1，b1，c1，d1，R4=a2，b2C1b1-，c4C2c1-，d2-，R5=a2，b2C1b1-，c5C2c1-，d2。這時(shí)可根據(jù)（a）中的情況進(jìn)行相似討論，得出矛盾。

（ii）當(dāng)b2=b1-時(shí)。

（a）假設(shè)b1-在V（C2）上的兩個(gè)出鄰點(diǎn)均不同于c1，設(shè)為c6和c7。因?yàn)镻1表示從d1到a1的路，P2表示從d2到a2的路。所以，我們構(gòu)造出3條路：R1=a1，b1，c1，d1，R6=a2，b1-，c6C2c1-，d2，R7=a2，b1-，c6C2c1-，d2。令C4*=P1∪R1，C5*=P2∪R6，C6*=P2∪R7，可知|V（C5*）|≠|(zhì)V（C6*）|，并且C5*和C6*均與C4*不相交，因此D存在兩個(gè)長(zhǎng)度不同且不相交的圈，與假設(shè)矛盾。

（b）假設(shè)c1=c7是b1-在V（C2）上的一個(gè)出鄰點(diǎn)，已知b1在V（C1）上的一個(gè)出鄰點(diǎn)，現(xiàn)在考慮a1在 V（C1）上的另一個(gè)出鄰點(diǎn)。我們首先證明a1在V（C1）上的另一個(gè)出鄰點(diǎn)不是b1+（b1+為b1在V（C1）上的后繼）。運(yùn)用反證法，不妨假設(shè)b1+是a1在V（C1）上的一個(gè)出鄰點(diǎn)。因?yàn)楝F(xiàn)在b1和b1-已是c1的兩個(gè)入鄰點(diǎn)，所以b1+在V（C2）上的兩個(gè)出鄰點(diǎn)都不同于c1，設(shè)為c8和c9。這時(shí)，b1+在V（C0）上存在不同于a1的入鄰點(diǎn)，設(shè)為a3（因?yàn)镈是三正則有向圖，a2在V（C1）上的兩個(gè)出鄰點(diǎn)為b1和b1-，所以a3≠a2）。另設(shè)a3在V（C1）上不同于b1+的出鄰點(diǎn)為b3（因?yàn)镈是三正則有向圖，所以b3不可能等于b1）。（1）b3≠b1-。這時(shí)，我們可知b3在V（C2）上的兩個(gè)出鄰點(diǎn)均不同于c1，設(shè)為c10和c11。又因?yàn)閍1≠a3，d1≠d2，可知在D＼[V（C1）∪V（C2）]上，也存在從{d1，d2}到{a1，a3}的兩條不相交的路，設(shè)為P3和P4。若P3是從d1到a1的路，P4是從d2到a3的路，那么我們構(gòu)造下面3條路：R1=a1，b1，c1，d1，R8=a3，b3，c10C2c1-，d2，R9=a3，b3，c11C2c1-，d2。令C7*=P3∪R1，C8*=P4∪R8，C9*=P4∪R9，可知|V（C8*）|≠|(zhì)V（C9*）|，并且C8*和C9*均與C7*不相交，因此D存在兩個(gè)長(zhǎng)度不同且不相交的圈，與假設(shè)矛盾。若P3是從d1到a3的路，P4是從d2到a1的路，那么我們可以得到這樣的路：R10=a1，b1b1+，c8C2c1-，d2，R11=a1，b1b1+，c9C2c1-，d2，R12=a3，b3C1b1-，c1，d1。令C10*=P3∪R12，C11*=P4∪R10，C12*=P4∪R11，可知|V（C11*）|≠|(zhì)V（C12*）|，并且C11*和C12*均與C10*不相交，因此D存在兩個(gè)長(zhǎng)度不同且不相交的圈，與假設(shè)矛盾。（2）若b3=b1-。因?yàn)閨V（Ci）|≥5，所以每個(gè)圈上至少有5個(gè)頂點(diǎn)，可以考慮b1+在V（C1）上的后繼b1++。此時(shí)，b1++在V（C0）上的兩個(gè)入鄰點(diǎn)均不同于a1，a2和a3，設(shè)其中一個(gè)為a4。并且a4在V（C1）上的兩個(gè)出鄰點(diǎn)均不同于b1，b1-和b1+，設(shè)其中一個(gè)為b4。另外，設(shè)b4在V（C2）上的兩個(gè)出鄰點(diǎn)為c12和c13，易知c12和c13均不同于c1。又因?yàn)閏1≠c4，d1≠d2，可知在D＼[V（C1）∪V（C2）]上，也存在從{d1，d2}到{a1，a4}的兩條不相交的路，設(shè)為P5和P6。若P5是從d1到a1的路，P6是從d2到a4的路，那么我們構(gòu)造下面3條路：R1=a1，b1，c1，d1，R13=a4，b4，c12C2c1-，d2，R14=a4，b4，c13C2c1-，d2。令C13*=P5∪R1，C14*=P6∪R13，C15*=P6∪R14，可知|V（C14*）|≠|(zhì)V（C15*）|，并且C14*和C15*均與C13*不相交，因此D存在兩個(gè)長(zhǎng)度不同且不相交的圈，與假設(shè)矛盾。若P5是從d1到a4的路，P6是從d2到a1的路。我們可以構(gòu)造這樣的路：R10=a1b1b1+，c8C2c1-，d2，R11=a1b1b1+，c9C2c1-，d2，R15=a4b4C1b1-，c1，d1。令C16*=P6∪R10，C17*=P6∪R11，C18*=P5∪R15，可知|V（C16*）|≠|(zhì)V（C17*）|，并且C16*和C17*均與C18*不相交，因此D存在兩個(gè)長(zhǎng)度不同且不相交的圈，與假設(shè)矛盾。所以，可知b1+不是a1在V（C1）上的出鄰點(diǎn)。設(shè)b5（b1+≠b5）是a1在V（C1）上的另一個(gè)不同于b1的出鄰點(diǎn)。因?yàn)榧僭O(shè)的是P1表示從d1到a1的路，P2表示從d2到a2的路。這時(shí)，D中可構(gòu)造出路：R16=a1b5C1b1-，c1，d1，R17=a2b1b1+，c8C2c1-，d2，R18=a2b1b1+，c9C2c1-，d2。令C19*=P1∪R16，C20*=P2∪R17，C21*=P2∪R18，可知|V（C20*）|≠|(zhì)V（C21*）|，并且C20*和C21*均與C19*不相交，因此D存在兩個(gè)長(zhǎng)度不同且不相交的圈，與假設(shè)矛盾。

其次，當(dāng)P1表示從d1到a2的路，P2表示從d2到a1的路時(shí)，也可經(jīng)過(guò)上述相似討論，證明D中存在兩個(gè)長(zhǎng)度不同且不相交的圈，與假設(shè)矛盾。

我們考慮了所有可能的情況，但均不可能發(fā)生，定理4是正確的。

——————————

參考文獻(xiàn)：

〔1〕BANG-JENSEN J， GUTIN G. Digraphs. Theory， Algorithms and Applications [M]. London： Springer–Verlag， 2001.

〔2〕TAN Ngo Dac. On 3-regular digraphs of girth 4 [J]. Discrete Mathematics， 2020， 343（01）：1–13.

〔3〕THOMASSEN C. Disjoint cycles in digraphs [J]. Combinatorica， 1983， 3（3-4）：393-396.

〔4〕LICHIARDOPOL N， PóR A，SERENI J-S. A Step toward the Bermond–Thomassen Conjecture about Disjoint Cycles in Digraphs [J]. Siam Journal on Discrete Mathematics， 2009， 23（02）：979-992.

〔5〕BAI Y， LI B， LI H.Vertex-disjoint cycles in bipartite tournaments [J]. Discrete Mathematics， 2015， 338 （08）： 1307–1309.

〔6〕LICHIARDOPOL N .Vertex-disjoint cycles in regular tournaments [J]. Discrete Mathematics， 2012， 312 （12-13）： 1927–1930.

〔7〕BANG-JENSEN J，BESSY S，THOMASSé S. Disjoint 3-Cycles in Tournaments： A? Proof of The Bermond-Thomassen Conjecture for Tournaments [J]. Journal of Graph Theory， 2014， 75（03）：284-302.

〔8〕GAO Y， MA D. Disjoint cycles with different length in 4-arc-dominated digraphs [J]. Operations Research Letters， 2013，41（06）：650-653.

〔9〕HENNING M A， YEO A. Vertex disjoint cycles of different length in digraphs [J]. SIAM Journal on Discrete Mathematics， 2012， 26（02）： 687–694.

〔10〕TAN Ngo Dac. On vertex disjoint cycles of different lengths in 3-regular digraphs [J]. Discrete Mathematics， 2015，338（12）：2485–2491.

〔11〕TAN Ngo Dac. On 3-regular digraphs without vertex disjoint cycles of different lengths [J]. Discrete Mathematics， 2017，340（08）： 1933–1943.