圍長為5的3-正則有向圖的不交圈

蔡曉霞 何志紅

摘 要：2017年Ngo Dac Tan提出了一個(gè)猜想：對每一個(gè)整數(shù)g≥3，只有有限多個(gè)圍長為g的3-正則有向圖不含不同長度的不交圈。g=3和g=4的情況在2017年和2020年分別被證明。本文主要證明了圍長為5的3-正則有向圖具有兩個(gè)不同長度的不交圈的存在性問題，給出了幾個(gè)充分條件。

關(guān)鍵詞：3-正則有向圖;圍長;不交圈

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

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

在整篇文章中，只考慮有限的簡單的有向圖，特殊標(biāo)注的地方除外。本文提到的有向圖的其他定義可以參考J. Bang-Jensen[1]的論述。

令D是一個(gè)有向圖。V（D）和A（D）分別表示它的點(diǎn)集合和弧集合，通常情況下也可以簡記為V和A。如果（u，v）∈A，則稱v是u的一個(gè)出鄰點(diǎn)，記u的所有出鄰點(diǎn)為ND+（u），u的出度是|ND+（u）|，記為dD+（u），即dD+（u）=|ND+（u）|，D的最小出度min{dD+（u）|u∈V}。類似地，稱u是v的一個(gè)入鄰點(diǎn)，記v的所有入鄰點(diǎn)為ND-（v），v的入度是|ND-（v）|，記為dD-（v），即dD-（v）=|ND-（v）|，D的最小入度為min{dD-（v）|v∈V}。如果U？哿V，那么由U生成的D的子有向圖記為D[U]。

令D=（V，A）是一個(gè)有向圖?；。╱，v）∈A簡記為uv，D中的圈和路通常指有向圈和有向路，D中的不交圈指點(diǎn)不交圈，如果C=v0，v1，…，vm-1，v0是D中長度為m的一個(gè)圈，那么viCvj的序列為vi，vi+1，vi+2，…，vj。viCvj既可以理解為是一條路，也可以理解為是一個(gè)點(diǎn)集合。圍長是指D中最短圈的長度。如果有向圖D中有dD+（v）=dD-（v）=k，且對V中任意的點(diǎn)都成立，那么我們稱D是k-正則圖。有向圖D=（V，A）的最小出度為d，如果對于弧集合A中的每一條弧uv都存在一個(gè)度為d的點(diǎn)x（x∈V）使得xu∈A，xv∈A，那么稱有向圖D為d-弧控制圖。如果有向圖D中不包含圈，那么我們稱D是無圈圖。

近幾年，有向圖中不交圈的存在條件是有向圖中的研究熱點(diǎn)。Thomassen[2]證明了最小出度至少是3的有向圖包含兩個(gè)不交圈。Henning和Yeo[3]提出了三個(gè)猜想，第一個(gè)猜想是最小出度至少是4的有向圖包含兩個(gè)不同長度的不交圈，第二個(gè)猜想是一個(gè)階數(shù)足夠大的3-正則有向圖包含兩個(gè)不同長度的不交圈，第三個(gè)猜想是每3-正則二部有向圖包含兩個(gè)不同長度的不交圈。Henning， Gao[3-5]在文獻(xiàn)中分別用不同的有向圖證明了第一個(gè)猜想。后來，Lichiardopol[6]完全證明了第一個(gè)猜想。第二個(gè)猜想Ngo Dac Tan[7]在文獻(xiàn)中有反例證明是不成立的，但這篇文章中構(gòu)造了一類無限的，不包含不同長度的不交圈的3-正則有向圖，定義如下：對任意的整數(shù)n≥2，點(diǎn)集合V（D2n2）={ui，vi|i=0，1，…，n-1}，弧集合A（D2n2）={uivi，viui，uiui+1，uivi+1，viui+1，vivi+1|i=0，1，…，n-1}，有向圖記為D2n2=（V（D2n2），A（D2n2））。同樣在這篇文獻(xiàn)中證明了第三個(gè)猜想對于不包含哈密爾頓路3-正則有向圖是成立的。Ngo Dac Tan[8]對3-弧控制有向圖包含兩個(gè)不同長度的不交圈進(jìn)行了證明。Ngo Dac Tan[9，10]在文獻(xiàn)中又分別對圍長為3和圍長為4的3-正則有向圖就行研究，給出了不交圈的存在條件。本文主要對圍長為5的3-正則有向圖進(jìn)行研究，假設(shè)有向圖D不包含不同長度的不交圈，證明了他在某些條件下的一般性結(jié)論，對研究圍長為5的3-正則有向圖不交圈的存在條件具有重要意義。

2 主要結(jié)論

定理2.1 D是一個(gè)圍長為5的3-正則有向圖，并且D中不包含不同長度的不交圈。令C′是D中長度為5的圈。D1=D-V（C′），P=p1，…，ps是D1中一條路。若ps在V（P）中有出鄰點(diǎn)，則ps-4（s≥5）是ps在V（P）中唯一的出鄰點(diǎn)。類似地，若p1在V（P）中有入鄰點(diǎn)，則p5（s≥5）是p1在V（P）中唯一的入鄰點(diǎn)。

證明 如果ps有一個(gè)出鄰點(diǎn)pi，pi∈V（P）且i≠s-4，則C1=pi，pi+1，…，ps，pi是D1中長度不同于5的一個(gè)圈。因此C′和C1是D中兩個(gè)不同長度的不交圈，與假設(shè)矛盾。因此，p4（s≥4）是p1在V（P）中唯一的出鄰點(diǎn)。類似地，也能證明p5（s≥5）是p1在V（P）中唯一的入鄰點(diǎn)。

定理2.2 D是一個(gè)圍長為5的3-正則有向圖，并且D中不包含不同長度的不交圈。令C′=x，y，z，u，w，x是D中的一個(gè)5-圈。D1=D-V（C′）。并且D1中沒有點(diǎn)的三個(gè)出鄰點(diǎn)都在都在V（C′）中，則

（1）D1中恰有五個(gè)點(diǎn)在V（C′）中分別恰有兩個(gè)出鄰點(diǎn)。

（2）D1中擁有出鄰點(diǎn)在V（C′）中的點(diǎn)在D1中構(gòu)成一個(gè)五圈。

證明 令T是D1中有出鄰點(diǎn)在V（C′）中的所有點(diǎn)的集合。因?yàn)镈是圍長為5的3-正則有向圖，所有很顯然T≠？覫。令P=a1，a2，…，as是D1中起點(diǎn)a1∈T的最長的一條路。由|V（P）|的最大性，as在D1中的所有出鄰點(diǎn)一定都在V（P）中。再由定理2.1可知，as最多有一個(gè)出鄰點(diǎn)在V（P）中，所以as在V（C′）中最少有兩個(gè)出鄰點(diǎn)。因?yàn)镈1中沒有點(diǎn)的三個(gè)出鄰點(diǎn)都在V（C′）中，所以as恰有兩個(gè)出鄰點(diǎn)在V（C′）中。也就是說，as-4一定是as的一個(gè)出鄰點(diǎn)。因此，C′0=as-4，as-3，as-2，as-1，as，as-4是D中的一個(gè)圈。

因?yàn)閍1∈T，所以a1至少有一個(gè)出鄰點(diǎn)在V（C′）中。不失一般性，我們可以假設(shè)x是a1的一個(gè)出鄰點(diǎn)，由定理2.1我們知道a1至多有一個(gè)入鄰點(diǎn)在V（P）中。因此，a1至少有兩個(gè)入鄰點(diǎn)在V（D）＼V（P）中。

假設(shè)a1≠as-4。如果a1有兩個(gè)入鄰點(diǎn)在V（C′）中，記這兩個(gè)點(diǎn)為n1和n2，則有C3=a1xC′n1，a1，C4=a1xC′n2，a1，可以看出C3和C4是兩個(gè)不同長度的圈，前面得到C′0=as-4，as-3，as-2，as-1，as，as-4，顯然C3和C4都不與C′0相交。所以，要么C3和C′0是D中兩個(gè)不同長度的不交圈，要么C4和C′0是D中兩個(gè)不同長度的不交圈。與假設(shè)矛盾。如果a1有至多一個(gè)入鄰點(diǎn)在V（C′）中，那么它一定有一個(gè)入鄰點(diǎn)在V（D）＼（V（P）∪V（C′））中。令X=x1，x2，…，xt是D2（D2=D-（V（P）∪V（C′）））中終點(diǎn)xt是a1的入鄰點(diǎn)的最長的一條路。由定理2.1得x1至多有一個(gè)入鄰點(diǎn)在V（P）∪V（X）中。因此，x1至少有兩個(gè)入鄰點(diǎn)在V（C′）中，我們記這兩個(gè)點(diǎn)為m1，m2，那么我們有C5=a1，xC′m1，a1，C6=a1，xC′m2，a1?？梢钥闯鯟5和C6是兩個(gè)不同長度的圈，并且C5和C6都不與C′0相交。因此，要么C5和C′0是D中兩個(gè)不同長度的不交圈，要么C6和C′0是D中兩個(gè)不同長度的不交圈，與假設(shè)矛盾。

因此，a1？芊as-4。這也就意味著D1中起點(diǎn)在T的最長路的長度為4。因?yàn)閍s∈T，A1=as，as-4，as-3，as-2，as-1是D1中長度為4的路并且起點(diǎn)as在T中，所以A1是D1中起點(diǎn)在T中的最長的路。因此，as-1一定有兩個(gè)出鄰點(diǎn)在V（C′）中，通過對路A2=as-1，as，as-4，as-3，as-2;A3=as-2，as-1，as，as-4，as-3;A4=as-3，as-2，as-1，as，as-4做重復(fù)類似的論證我們可以得到as-2，as-3，as-4在V（C0）中有兩個(gè)出鄰點(diǎn)。從而as，as-1，as-2，as-3，as-4是D1中有出鄰點(diǎn)在V（C0）中的所有點(diǎn)（因?yàn)榍∮?0條弧從D1到V（C′）），并且他們中的每一個(gè)點(diǎn)都恰有兩個(gè)出鄰點(diǎn)在V（C′）中。由前面我們知道C′0=as-4，as-3，as-2，as-1，as，as-4是一個(gè)圈，所以他們構(gòu)成一個(gè)5-圈。

由定理2.2馬上得到下面的定理2.3。

定理2.3 D是一個(gè)圍長為5的3-正則有向圖，并且D中不包含不同長度的不交圈。令C′=x，y，z，u，w，x是D中的一個(gè)5-圈。D1=D-V（C′）。并且D1中沒有點(diǎn)的三個(gè)入鄰點(diǎn)都在V（C′）中，則

（1）D1中恰有五個(gè)點(diǎn)在V（C′）中分別恰有兩個(gè)入鄰點(diǎn)。

（2）D1中擁有入鄰點(diǎn)在V（C′）中的點(diǎn)在D1中構(gòu)成一個(gè)5-圈。

若D1中有一個(gè)點(diǎn)x1的三個(gè)入鄰點(diǎn)都在V（C′）中。令xj（xj∈V（D1），xj≠x1）有一個(gè)入鄰點(diǎn)在V（C′）中。記A1，j={x1，xj}。假設(shè)r1，r2是D1中僅有的有三個(gè)出鄰點(diǎn)在V（C′）中的點(diǎn)。記B={r1，r2}。

定理2.4 D是一個(gè)圍長為5的3-正則有向圖，并且D中不包含不同長度的不交圈。令C′=x，y，z，u，w，x是D中的一個(gè)5-圈。D1=D-V（C′）。D1中有一個(gè)點(diǎn)x1，它的三個(gè)入鄰點(diǎn)都在V（C′）中。那么對任意的不動(dòng)子集A1，j，D1中有兩條從A1，j到B的不交路。

證明 已知r1，r2是D1中僅有的有三個(gè)出鄰點(diǎn)在V（C′）中的點(diǎn)，因?yàn)榍∮?0條弧從V（D1）到V（C′），所以D1中有出鄰點(diǎn)在V（C′）中的點(diǎn)可以分為下面三種情況：（1）r3，r4各恰有兩個(gè)出鄰點(diǎn)在V（C′）中。（2）r3，r4，r5，r6各恰有一個(gè)出鄰點(diǎn)在V（C′）中。（3）r3有兩個(gè)出鄰點(diǎn)在V（C′）中，r4，r5各恰有一個(gè)出鄰點(diǎn)在V（C′）中。我們假設(shè)在（1）中r3不是r4的出鄰點(diǎn)，r4也不是r3的出鄰點(diǎn)且r3的入鄰點(diǎn)不是r4的入鄰點(diǎn)。同樣地，r4的入鄰點(diǎn)不是r3的入鄰點(diǎn)。假設(shè)在（3）中r3不是r4，r5的出鄰點(diǎn)。要證對任意的不動(dòng)子集A1，j，D1中有兩條從A1，j到B的不交路，那么先來證對于任意的點(diǎn)x∈D1，D1中有條從A1，j到B的路是避開x的。

首先假設(shè)x=x1。令P=a1，a2，…，dl且d1=xj是D1中起點(diǎn)為xj的最長的一條路。因?yàn)镈的圍長為5，不難發(fā)現(xiàn)xj至少有一個(gè)出鄰點(diǎn)在V（D1）中。因此，l≥2。由定理2.1可知，dl一定至少有兩個(gè)出鄰點(diǎn)在V（C′）中。因此，要么dl∈B，要么dl是情況（1）中的r3（或者r4，不失一般性，我們假設(shè)dl=r3）或者情況（3）中的r3。因?yàn)閤1的三個(gè)入鄰點(diǎn)都在V（C′）中，所以x1？埸V（P）。如果dl∈B，則P是D1中從A1，j到B避開x1的一條路?，F(xiàn)在我們考慮情況（1）中的r3即dl=r3，這種情況下先來看dl-1，因?yàn)閐l-1≠r1，r2，r3且由已知條件dl-1≠r4，所以dl-1沒有出鄰點(diǎn)在V（C′）中。因?yàn)閐l-1至多有兩個(gè)出鄰點(diǎn)在V（P）中，所以它一定有一個(gè)出鄰點(diǎn)g∈V（D1＼V（P）。則P′=d1，d2，…，dl-1，g是D1中起點(diǎn)為xj的最長的一條路。因此g一定有至少兩個(gè)出鄰點(diǎn)在V（C′）中。因?yàn)間≠r3，由已知條件g≠r4，所以g∈B。因此，P′是D1中從A1，j到B避開x1的一條路。

下面我們考慮情況（3）中的r3即dl=r3（r3有兩個(gè)出鄰點(diǎn)在V（C′）中，r4，r5各恰有一個(gè)出鄰點(diǎn)在V（C′）中）。同樣先來看dl-1，由已知dl-1≠r4，r5，因?yàn)閐l-1至多有兩個(gè)出鄰點(diǎn)在V（P）中，所以dl-1一定有一個(gè)出鄰點(diǎn)g′∈V（D1＼V（P）。那么P"=d1，d2，…，dl-1，g′是D1中起點(diǎn)為xj的最長的一條路。因此，g′一定至少有兩個(gè)出鄰點(diǎn)在V（C′）中，因?yàn)間′≠r3，所以g′∈B。因此，P"是D1中從A1，j到B避開x1的一條路。

接下來假設(shè)x≠x1。D2=D-（V（C′）∪{x}），則x1∈V（D2）。令T是D1中起點(diǎn)為x1的所有路的集合。因?yàn)閤1至少有一個(gè)出鄰點(diǎn)在D2中，所以顯然T≠？覫?，F(xiàn)在我們來證明T中至少有一條路包含B＼{x}中的一個(gè)點(diǎn)。

采用反證法，假設(shè)T中沒有路包含B＼{x}中的一個(gè)點(diǎn)，令V′={v∈V（D2）|v是D2中能從x1到達(dá)的點(diǎn)}。接下來需要先證明D2[V′]是無圈的。選擇一個(gè)點(diǎn)r∈B＼{x}，那么r至少有兩個(gè)出鄰點(diǎn)在V（C′）中，記這兩個(gè)點(diǎn)為s1，s2。因?yàn)門中沒有路包含B＼{x}中的一個(gè)點(diǎn)，所以一定有r？埸V′。假設(shè)Y=y1，y2，…，ys是D2中終點(diǎn)ys=r的最長的一條路。因?yàn)閞至少有兩個(gè)入鄰點(diǎn)在D2中，所以顯然s≥2。由定理2.1可知y1至少有兩個(gè)入鄰點(diǎn)在V（C′）∪{x}中。因此，y1至少有一個(gè)入鄰點(diǎn)在V（C′）中，記這個(gè)點(diǎn)為s3。令P1=r，s1，C′，s3;P2=r，s2，C′，s3，y1，記C1=Y∪P1，C2=Y∪P2，則C1，C2是V（Y）∪V（C′）中兩個(gè)不同長度的圈。因?yàn)閤1到不了Y中的點(diǎn)，否則x1能到達(dá)r，與前提條件矛盾，所以V′∩V（Y）∪V（C′））=？覫。因此，若D2[V′]中有個(gè)圈C3，則要么C1和C3是D中兩個(gè)不同長度的不交圈，要么C2和C3是D中兩個(gè)不同長度的不交圈，與假設(shè)矛盾。因此，D2[V′]是無圈的。

假設(shè)E=e1，e2，…，ei是T中最長的一條路，其中e1=x1，顯然i≥2。由定理2.1可知，至少有兩個(gè)出鄰點(diǎn)在V（C′）中，因?yàn)镾中沒有路包含B＼{x}中的點(diǎn)，且D2[V′]是無圈的，所以不難發(fā)現(xiàn)ei？埸B＼{x}，ei有兩個(gè)出鄰點(diǎn)在V（C′）中并且ei是x的一個(gè)入鄰點(diǎn)。因此，由前面提到的情況（1）和情況（3），下面需要考慮關(guān)于ei的兩種情況。（I）：ei=r3（r3，r4各恰有兩個(gè)出鄰點(diǎn)在V（C′）中）。因?yàn)閞1，r2有3個(gè)出鄰點(diǎn)在V（C′）中，所以他們不在V（E）中，又因?yàn)閞4不是r3的出鄰點(diǎn)，所以ei-1≠r1，r2，r3，r4，這意味著ei-1沒有出鄰點(diǎn)在V（C′）中。此外，如果ei-5是ei-1的一個(gè)出鄰點(diǎn)，那么我們能在D2[V′]中得到一個(gè)圈ei-5，ei-4，ei-3，ei-2，ei-1，ei-5，與D2[V′]是無圈的矛盾。因此，ei-5不是ei-1的出鄰點(diǎn)，那么ei-1一定有一個(gè)出鄰點(diǎn)s∈V（D2）＼V（E），則E′=e1，e2，…，ei-1，s是T中最長的一條路。因?yàn)镈2[V′]是無圈的，所以s沒有出鄰點(diǎn)在V（E′）中。那么s一定有三個(gè)出鄰點(diǎn)在V（C′）∪{x}中。又因?yàn)閟≠r4并且s≠r3，由此斷定s∈B＼{x}，這與前面假設(shè)的T中沒有路包含B＼{x}中的一個(gè)點(diǎn)矛盾。再來看（II）：ei=r3（r3有兩個(gè)出鄰點(diǎn)在V（C′）中，r4，r5各恰有一個(gè)出鄰點(diǎn)在V（C′）中）。同樣地，因?yàn)閞1，r2有3個(gè)出鄰點(diǎn)在V（C′）中，所以他們不在V（E）中。又因?yàn)閞4，r5不是r3的出鄰點(diǎn)，所以ei-1≠r1，r2，r3，r4，r5，這意味著ei-1沒有出鄰點(diǎn)在V（C′）中。因?yàn)镈2[V′]是無圈的，所以ei-5不是ei-1的出鄰點(diǎn)。那么ei-1一定有一個(gè)出鄰點(diǎn)s∈V（D2）＼V（E），則E′=e1，e2，…，ei-1，s是T中最長的一條路，并且s的出鄰點(diǎn)沒有在V（E′）中的。那么s一定有三個(gè)出鄰點(diǎn)在V（C′）∪{x}中，所以s∈B＼{x}，這與假設(shè)的T中沒有路包含B＼{x}中的一個(gè)點(diǎn)矛盾。因此，假設(shè)T中沒有路包含B＼{x}中的一個(gè)點(diǎn)是錯(cuò)誤的，這也就意味著存在一條路是從x1到B且避開x的。

綜上證明出對于任意的點(diǎn)x∈V（D1），V（D1）中都有一條從A1，j到B避開x的一條路。再由Menger's Theorem，V（D1）中有兩條從A1，j到B的不交路。

由定理2.3可知，D1中有5個(gè)點(diǎn)x1，x2，x3，x4和x5，他們有入鄰點(diǎn)在C′中，并且他們中每個(gè)點(diǎn)都恰有兩個(gè)入鄰點(diǎn)在C′中。此外，他們還構(gòu)成一個(gè)5-圈。不失一般性，假設(shè)這個(gè)5-圈為C=x1，x2，x3，x4，x5，x1，我們記Ai，j={xi，xj}（i，j∈{1，2，3，4，5}）。

引理2.1[10] D是一個(gè)圍長為4的3-正則有向圖，并且D中不包含不同長度的不交圈。令C0=a0，b0，c0，d0，d0是D中的一個(gè)四圈。D′=D-V（C0）。假設(shè)={xi，xj}和B={r1，r2}是D′的子集合，且在V（D′）中有兩條從Ai，j到Q1的不交路。則D-A（D′）不包含從Ai，j到Q1的路Q1，Q2，Q3，Q′1，Q′2，Q′3，這六條路具有以下性質(zhì)：

（a）Q1和Q2不同長度且都不與Q3相交。

（b）Q′1和Q′2不同長度且都不與Q′3相交。

（c）Q1和Q2的起點(diǎn)都是u1，終點(diǎn)都是xi，而Q3的起點(diǎn)是u2，終點(diǎn)都是xj。

（d）要么Q′1和Q′2的起點(diǎn)都是u1，終點(diǎn)都是xj，而Q3的起點(diǎn)是u2，終點(diǎn)都是xi，要么Q′1和Q′2的起點(diǎn)都是u2，終點(diǎn)都是xi，而Q3的起點(diǎn)是u1，終點(diǎn)都是xj。

引理2.1的結(jié)果同樣適用于圍長為5的情況，證明過程不在這里贅述。

定理2.5 D是一個(gè)圍長為5的3-正則有向圖，并且D中不包含不同長度的不交圈。令C′=x，y，z，u，w，x是D中的一個(gè)5-圈且D1=D-V（C′）。D1中有一個(gè)點(diǎn)x1，它的三個(gè)入鄰點(diǎn)都在V（C′）中。則如果D1中有一個(gè)點(diǎn)的三個(gè)出鄰點(diǎn)都在V（C′）中，那么D1中這樣的點(diǎn)是唯一的。

證明 假設(shè)D1中有一個(gè)點(diǎn)r1的三個(gè)出鄰點(diǎn)都在V（C′）中，此外D1還擁有另一個(gè)點(diǎn)r2，它的三個(gè)出鄰點(diǎn)也都在V（C′）中。由定理2.4可知剩下的D1中有出鄰點(diǎn)在V（C′）中的點(diǎn)可以分為三種情況，并且對任意的不動(dòng)子集A1，j，D1中有兩條從A1，j到B的不交路。

下面對V（C′）中的點(diǎn)重新命名，C′=a0，b0，c0，d0，e0，a0。不失一般性可以假設(shè)ND+（r1）={a0，b0，c0}。此外，根據(jù)r2出鄰集中的點(diǎn)和x1入鄰集中的點(diǎn)，選擇D1中一個(gè)合適的點(diǎn)xj（xj≠x1），且xj有入鄰點(diǎn)在V（C′）中，x1，xj構(gòu)成集合A1，j。則可以證明在D-A（D1）中存在從B到A1，j的路H1，H2，H3，H′1，H′2，H′3，這六條路具有以下性質(zhì)：

（a）H1和H2不同長度且都不與H3相交。

（b）H′1和H′2不同長度且都不與H′3相交。

（c）H1和H2的起點(diǎn)都是r1，終點(diǎn)都是x1，而H3的起點(diǎn)是r2，終點(diǎn)都是xj。

（d）H′1和H′2的起點(diǎn)都是r1，終點(diǎn)都是xj，而H3的起點(diǎn)是r2，終點(diǎn)都是x1。

情況一 ND+（r2）={a0，b0，c0}（resp.，ND+（r2）={b0，c0，d0}，ND+（r2）={b0，c0，e0}。

如果ND-（x1）={a0，c0，d0}或ND-（x1）={b0，c0，d0}或ND-（x1）={c0，d0，e0}，那么我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，c0，x1;H2=r1，c0，d0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，x1。

如果ND-（x1）={a0，b0，d0}或ND-（x1）={a0，d0，e0}，那么我們從D1中選a0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，a0，x1;H2=r1，c0，d0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，x1。

如果ND-（x1）={a0，b0，c0}或ND-（x1）={b0，c0，e0}，那么我們從D1中選a0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，b0，x1;H2=r1，b0，c0，x1;H3=r2，d0，e0，a0，xj（resp.，H3=r2，e0，a0，xj;H3=r2，a0，xj）;H′1=r1，a0，xj;H′2=r1，c0，d0，e0，a0，xj;H′3=r2，b0，x1。

如果ND-（x1）={a0，c0，e0}或ND-（x1）={a0，b0，e0}，那么我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，a0，x1;H2=r1，c0，d0，e0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，d0，e0，x1。

如果ND-（x1）={b0，d0，e0}，那么我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到H1=r1，c0，d0，x1;H2=r1，c0，d0，e0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，d0，x1。

情況二 ND+（r2）={a0，b0，d0}（resp.，ND+（r2）={a0，b0，e0}。

如果ND-（x1）={a0，b0，c0}或ND-（x1）={a0，b0，d0}或ND-（x1）={a0，b0，e0}，那么我們從D1中選e0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，a0，x1;H2=r1，a0，b0，x1;H3=r2，d0，e0，xj（resp.，H3=r2，e0，xj）;H′1=r1，c0，d0，e0，xj;H′2=r1，b0，c0，d0，e0，xj;H′3=r2，a0，x1。

如果ND-（x1）={a0，d0，e0}或ND-（x1）={b0，d0，e0}或ND-（x1）={c0，d0，e0}，那么我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，c0，d0，x1;H2=r1，c0，d0，e0，x1;H3=r2，b0，xj;H′1=r1，b0，e0，xj;H′2=r1，a0，b0，xj;H′3=r2，d0，x1（resp.，H′3=r2，e0，xj）。

如果ND-（x1）={a0，c0，d0}或ND-（x1）={a0，c0，e0}，那么我們從D1中選e0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，c0，x1;H2=r1，b0，c0，x1;H3=r2，d0，e0，xj（resp.，H3=r2，e0，xj）;H′1=r1，c0，d0，e0，xj;H′2=r1，b0，c0，d0，e0，xj;H′3=r2，a0，x1。

如果ND-（x1）={b0，c0，d0}或ND-（x1）={b0，c0，e0}，那么我們從D1中選a0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，b0，x1;H2=r1，b0，c0，x1;H3=r2，a0，xj;H′1=r1，a0，xj;H′2=r1，c0，d0，e0，a0，xj;H′3=r2，b0，x1。

情況三 ND+（r2）={a0，c0，d0}（resp.，ND+（r2）={a0，c0，e0}）。

如果ND-（x1）={a0，b0，c0}或ND-（x1）={a0，b0，d0}或ND-（x1）={a0，b0，e0}，那么我們從D1中選c0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到H1=r1，a0，x1;H2=r1，a0，b0，x1;H3=r2，c0，xj;H′1=r1，c0，xj;H′2=r1，b0，c0，xj;H′3=r2，a0，x1。

如果ND-（x1）={a0，d0，c0}或ND-（x1）={b0，d0，e0}或ND-（x1）={c0，d0，e0}，那么我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，c0，d0，x1;H2=r1，c0，d0，e0，x1;H3=r2，a0，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，d0，x1。

如果ND-（x1）={a0，c0，d0}或ND-（x1）={b0，c0，d0}，那么我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，c0，x1;H2=r1，c0，d0，x1;H3=r2，a0，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，x1。

如果ND-（x1）={a0，c0，e0}或ND-（x1）={b0，c0，e0}，那么我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，c0，x1;H2=r1，c0，d0，e0，x1;H3=r2，a0，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，c0，x1。

情況四 ND+（r2）={a0，d0，e0}（resp.，ND+（r2）={b0，d0，e0}，ND+（r2）={c0，d0，e0}）。

如果ND-（x1）={a0，d0，c0}或ND-（x1）={a0，d0，d0}或ND-（x1）={a0，d0，e0}，那么我們從D1中選d0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，a0，x1;H2=r1，a0，b0，x1;H3=r2，d0，xj;H′1=r1，c0，d0，xj;H′2=r1，b0，c0，d0，xj;H′3=r2，e0，a0，x1。

如果ND-（x1）={a0，c0，d0}或ND-（x1）={b0，c0，d0}或ND-（x1）={c0，d0，e0}，那么我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到H1=r1，c0，x1;H2=r1，c0，d0，x1;H3=r2，e0，a0，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，d0，x1。

如果ND-（x1）={b0，c0，e0}或ND-（x1）={b0，d0，e0}，那么我們從D1中選d0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，b0，x1;H2=r1，a0，b0，x1;H3=r2，d0，xj;H′1=r1，c0，d0，xj;H′2=r1，b0，c0，d0，xj;H′3=r2，e0，x1。

如果ND-（x1）={a0，c0，e0}，那么我們從D1中選d0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，a0，x1;H2=r1，b0，c0，x1;H3=r2，d0，xj;H′1=r1，c0，d0，xj;H′2=r1，b0，c0，d0，xj;H′3=r2，e0，x1。

當(dāng)ND-（x1）={a0，d0，e0}，ND+（r2）={a0，d0，e0}時(shí)，我們從D1中選e0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，c0，d0，x1;H2=r1，b0，c0，d0，x1;H3=r2，e0，xj;H′1=r1，c0，d0，e0，xj;H′2=r1，b0，c0，d0，e0，xj;H′3=r2，a0，x1。

當(dāng)ND-（x1）={a0，d0，e0}，ND+（r2）={b0，d0，e0}時(shí)，我們從D1中選b0的一個(gè)出鄰點(diǎn)xj（xj≠x1），x1，xj構(gòu)成集合A1，j，并且能夠得到：H1=r1，a0，x1;H2=r1，c0，d0，x1;H3=r2，b0，xj;H′1=r1，b0，xj;H′2=r1，a0，b0，xj;H′3=r2，e0，x1。

當(dāng)ND-（x1）={a0，d0，e0}，ND+（r2）={c0，d0，e0}時(shí)，從B到A1，j的路H1，H2與H3會(huì)存在交點(diǎn)，所以結(jié)論成立必須當(dāng)ND+（r2）={c0，d0，e0}時(shí)，ND-（x1）≠{a0，d0，e0}。

參考文獻(xiàn)：

〔1〕J. Bang-Jensen， G. Gutin， Digraphs： Theory， Algorithms and Applications[M]. Springer， London， 2001.

〔2〕C.Thomassen， Disjoint cycles in digraphs[J]. Combinatorica， 1983， 3： 393-396.

〔3〕M.A. Henning， A.Yeo， Vertex disjoint cycles of different length in digraphs[J]. SIAM J. Discrete Math， 2012， 26： 687-694.

〔4〕Y.Gao， D.Ma， Disjoint cycles with different length in 4-arc-dominated digraphs[J]. Oper.Res.Lett， 2013， 41： 650-653.

〔5〕Ngo Dac Tan， Vertex disjoint cycles of different length in d-arc-dominated digraphs[J]. Oper.Res.Lett， 2014， 42： 351-354.

〔6〕N.Lichiardopol， Proof of a conjecture of Henning and Yeo on vertex-disjoint directed cycles[J]. SIAM J. Discrete Math， 2014， 28： 1618-1627.

〔7〕Ngo Dac Tan， On vertex disjoint cycles of different lengths in 3-regular digraphs[J]. Discrete Math， 2015， 338： 2485-2491.

〔8〕Ngo Dac Tan， 3-arc-dominted digraphs [J]. SIAM J. Discrete Math， 2010， 24： 1153-1161.

〔9〕Ngo Dac Tan， On 3-regular digraphs without vertex disjoint cycles of different lengths[J]. Discrete Math， 2017， 340： 1933-1943.

〔10〕Ngo Dac Tan， On 3-regular digraphs of girth 4[J]. Discrete Math， 2020， 343： 1-13.