正则有向图中的不相交圈

程攀攀 何志红

摘 要：2020年，Tan提出猜想：所有的三正则有向图除D73，D83和D2n2外都包含两个不同长度且不相交的圈。Tan证明了围长为3和4的三正则有向图对于这个猜想均成立。受此启发，本文证明这个猜想对于围长为5且具有至少4个圈的圈因子的三正则有向图也是成立的。

关键词：三正则有向图;圈因子;不交圈

中图分类号：O157.6  文献标识码：A  文章编号：1673-260X（2021）01-0001-03

1 引言与预备知识

设D=（V，A）为一有向图，其中顶点集合为V（D）（或简写为V），弧集合为A（D）（或简写为A），除特别说明外，本文中研究的有向图均为有限简单有向图（不包含多重弧和自环），关于有向图用到的符号见参考文献[1]。

对于有向图D中的任意一个顶点v，定义如下集合

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

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

这里ND+（v）表示顶点v的出邻集，ND-（v）表示顶点v的入邻集，ND+（v）和ND-（v）中的顶点分别表示v的出邻点和入邻点。dD+（v）表示顶点v的出度，即v的出邻点个数（dD+（v）=|ND+（v）|），ND-（v）表示顶点v的入度，即v的入邻点的个数（ND-（v）=|ND-（v）|）。若对D中任意一个顶点v都有dD+（v）=dD-（v），则称有向图D为k正则有向图。

本文中提到的圈（路）均为有向圈（路），不相交的圈指的是顶点不相交的圈，围长是指一个有向图中最短圈的长度。如果u∈V（C），则用u-和u+分别表示C上u的前趋和后继，同样的，u- -和u++分别表示C上u-的前趋和u+的后继。若F=C1∪C2∪…∪Ct为有向图D的生成有向子图且C1，C2，…，Ct为两两不相交的圈，则称F为有向图D的一个圈因子。如果C=v0v1…vl-1v0是D中一个长度为l的圈，并且vi，vj∈V（C），这时viCvj表示的是vi，vi+1，vi+2，…，vj（指标模l）这个有序列。另外，根据文献[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}（这里的指标是模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]等研究了有向圖中不交圈的问题，还有一些文献[5-7]研究了竞赛图中不交圈问题，但是没有考虑圈的长度.在近几年的研究中，许多研究者对有向图中是否存在两个长度不同且不相交的圈问题十分感兴趣，Gao和Ma[8]证明了一类4-弧-控制有向图包含两个长度不同且不相交的圈，下面我们再介绍几个相关的猜想和定理。

猜想1（Henning和Yeo[9]） 每一个三正则二部有向图均包含两个长度不同且不相交的圈。

猜想2（Tan[2]） 所有的三正则有向图除D73，D83和D2n2外都包含两个长度不同且不相交的圈。

定理1（Tan[10]） 每个具有至少两个圈因子的三正则二部有向图都包含两个长度不同且不相交的圈。

定理2（Tan[11]） 如果D是围长为3的三正则有向图，则D不包含两个长度不同且不相交的圈当且仅当D和D73或D83同构。

定理3（Tan[2]） 每一个围长为4的三正则有向图都包含两个长度不同且不相交的圈。

对于猜想2，Tan[2，11]证明了三正则有向图的围长为3和4时都是成立的。受Tan[10]的启发，我们证明了每一个具有至少4个圈的圈因子的三正则有向图当围长为5时都包含两个长度不同且不相交的圈，即本文中的定理4。

2 主要结果

定理4 每一个围长为5且具有至少4个圈的圈因子的三正则有向图D都包含两个长度不同且不相交的圈。

证明 设F=C0∪C1∪…∪Cl-1为D的一个圈因子且l≥4。因为D的围长为5，所以|V（Ci）|≥5（i=0，1，2，…，l-1）。显然，如果这些圈因子中，存在两个圈的长度不同或者存在一个圈Ci（0≤i≤l-1）内部有弦，结论是成立的。由此，只需考虑圈因子中所有圈的长度均相等且每个圈都是无弦时的情况，即 |V（C0）|=|V（C1）|=…=|V（Cl-1）|=k≥5。因为D是三正则有向图，所以圈Ci上的每个顶点都恰有两个出邻点和两个入邻点在V（D）＼V（Ci）（指标模l）上。运用反证法，假设定理4是错误的，即其所有不交圈的长度均相等。通过Tan[10]文章中的Claim 2可知D中所有的弧都是从Ci到Ci+1上的（这里的指标都是模l的），且Henning和Yeo[9]文章中的Claim Ⅲ可知对于D中任意两个顶点的集合{a1，a2}？哿V（C0）以及{d1，d2}？哿V（C3），在D＼[V（C1（∪V（C2）]上存在从{d1，d2}到{a1，a2}的两条不相交的路。

我们在C1上任选一个点b1，设a1和a1为b1在V（C0）上的两个入邻点，c1为b1在V（C2）上的出邻点，d1为c1在V（C3）上的出邻点。设b1-为b1在V（C1）上的前趋，c1-为c1在V（C2）上的前趋。因为D是三正则有向图，所以c1-在V（C3）上的出邻点至少有一个不同于d1，设为d2。此时，a1≠a2，d1≠d2，可知在  D＼[V（C1）∪V（C2）]上，从{d1，d2}到{a1，a2}存在两条不相交的路，设为P1和P2。首先，假设P1表示从d1到a1的路，P2表示从d2到a2的路。由此，设a2在V（C1）上且不同于b1的出邻点为b2。

（i）当b2≠b1-时。

（a）若b2在V（C2）上的两个出邻点c2和c3均不同于c1，那么我们构造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*）| ≠|V（C3*）|，并且C3*和C3*均与C1*不相交，因此可找到两个长度不同且不相交的圈，与假设矛盾。

（b）若c1是b2在V（C2）上的一个出邻点，那么b1-在V（C2）上的两个出邻点均不同于c1，设为c4和c5。可构造下面3条路：R1=a1，b1，c1，d1，R4=a2，b2C1b1-，c4C2c1-，d2-，R5=a2，b2C1b1-，c5C2c1-，d2。这时可根据（a）中的情况进行相似讨论，得出矛盾。

（ii）当b2=b1-时。

（a）假设b1-在V（C2）上的两个出邻点均不同于c1，设为c6和c7。因为P1表示从d1到a1的路，P2表示从d2到a2的路。所以，我们构造出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*）|≠|V（C6*）|，并且C5*和C6*均与C4*不相交，因此D存在两个长度不同且不相交的圈，与假设矛盾。

（b）假设c1=c7是b1-在V（C2）上的一个出邻点，已知b1在V（C1）上的一个出邻点，现在考虑a1在 V（C1）上的另一个出邻点。我们首先证明a1在V（C1）上的另一个出邻点不是b1+（b1+为b1在V（C1）上的后继）。运用反证法，不妨假设b1+是a1在V（C1）上的一个出邻点。因为现在b1和b1-已是c1的两个入邻点，所以b1+在V（C2）上的两个出邻点都不同于c1，设为c8和c9。这时，b1+在V（C0）上存在不同于a1的入邻点，设为a3（因为D是三正则有向图，a2在V（C1）上的两个出邻点为b1和b1-，所以a3≠a2）。另设a3在V（C1）上不同于b1+的出邻点为b3（因为D是三正则有向图，所以b3不可能等于b1）。（1）b3≠b1-。这时，我们可知b3在V（C2）上的两个出邻点均不同于c1，设为c10和c11。又因为a1≠a3，d1≠d2，可知在D＼[V（C1）∪V（C2）]上，也存在从{d1，d2}到{a1，a3}的两条不相交的路，设为P3和P4。若P3是从d1到a1的路，P4是从d2到a3的路，那么我们构造下面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*）|≠|V（C9*）|，并且C8*和C9*均与C7*不相交，因此D存在两个长度不同且不相交的圈，与假设矛盾。若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*）|≠|V（C12*）|，并且C11*和C12*均与C10*不相交，因此D存在两个长度不同且不相交的圈，与假设矛盾。（2）若b3=b1-。因为|V（Ci）|≥5，所以每个圈上至少有5个顶点，可以考虑b1+在V（C1）上的后继b1++。此时，b1++在V（C0）上的两个入邻点均不同于a1，a2和a3，设其中一个为a4。并且a4在V（C1）上的两个出邻点均不同于b1，b1-和b1+，设其中一个为b4。另外，设b4在V（C2）上的两个出邻点为c12和c13，易知c12和c13均不同于c1。又因为c1≠c4，d1≠d2，可知在D＼[V（C1）∪V（C2）]上，也存在从{d1，d2}到{a1，a4}的两条不相交的路，设为P5和P6。若P5是从d1到a1的路，P6是从d2到a4的路，那么我们构造下面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*）|≠|V（C15*）|，并且C14*和C15*均与C13*不相交，因此D存在两个长度不同且不相交的圈，与假设矛盾。若P5是从d1到a4的路，P6是从d2到a1的路。我们可以构造这样的路：R10=a1b1b1+，c8C2c1-，d2，R11=a1b1b1+，c9C2c1-，d2，R15=a4b4C1b1-，c1，d1。令C16*=P6∪R10，C17*=P6∪R11，C18*=P5∪R15，可知|V（C16*）|≠|V（C17*）|，并且C16*和C17*均與C18*不相交，因此D存在两个长度不同且不相交的圈，与假设矛盾。所以，可知b1+不是a1在V（C1）上的出邻点。设b5（b1+≠b5）是a1在V（C1）上的另一个不同于b1的出邻点。因为假设的是P1表示从d1到a1的路，P2表示从d2到a2的路。这时，D中可构造出路：R16=a1b5C1b1-，c1，d1，R17=a2b1b1+，c8C2c1-，d2，R18=a2b1b1+，c9C2c1-，d2。令C19*=P1∪R16，C20*=P2∪R17，C21*=P2∪R18，可知|V（C20*）|≠|V（C21*）|，并且C20*和C21*均与C19*不相交，因此D存在两个长度不同且不相交的圈，与假设矛盾。

其次，当P1表示从d1到a2的路，P2表示从d2到a1的路时，也可经过上述相似讨论，证明D中存在两个长度不同且不相交的圈，与假设矛盾。

我們考虑了所有可能的情况，但均不可能发生，定理4是正确的。

——————————

参考文献：

〔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.