超欧拉和双有向迹的强积有向图

崔秋月, 刘 娟, 董畅畅

(新疆师范大学 数学科学学院, 新疆 乌鲁木齐 830017)

下面介绍了强积有向图的定义.

定义1令D1=(V1,A1)和D2=(V2,A2)是2个有向图,V1={u1,u2,…,un1},V2={v1,v2,…,vn2},则D1和D2的强积有向图定义如下:强积有向图记作D1⊗D2,其点集为V1×V2,任意2个不同的点(ui,vj)和(us,vt),若((ui,vj),(us,vt))∈A(D1⊗D2)当且仅当以下3个条件之一成立:

1)ui=us且(vj,vt)∈A2;

2)vj=vt且(ui,us)∈A1;

3) (ui,us)∈A1且(vj,vt)∈A2.

Boesch等[3]在1977年提出了超欧拉问题,他们致力于刻画出包含生成欧拉子图的无向图,同时,他们表示这个问题是非常困难的.Pulleyblank[4]在1979年证明了判定一个无向图(甚至包含平面无向图)是否是超欧拉的条件是NP-完备性.截至今日,已经有大量关于超欧拉无向图的研究,例如Catlin的研究[5]和文献[6-7].

在文献[13]中,一个开放性的问题(问题6)被提出,关于寻找使得无向图的积图成为哈密尔顿图的条件.受此问题的启发,本文提出寻找使得2个有向图的积图成为超欧拉有向图的条件.文献[14]研究了对于给定直径，有向图超欧拉的充分条件.本文将研究关于2个有向图的强积图成为超欧拉有向图或双有向迹有向图的充分条件.

1 符号

命题1.1令D1=(V1,A1)和D2=(V2,A2)是两个有向图,V1={u1,u2,…,un1},V2={v1,v2,…,vn2},则下面的每一条都成立:

2 强积有向图

下面介绍的引理2.1将被应用在证明一个有向图是非超欧拉有向图的例子上.

引理2.1[15]对于某个正整数m和一个有向图D,如果V(D)包含点不交的子集B,B1,…,Bm且满足以下2个条件:

1)N-(Bi)⊆B,i∈[m];

2) |∂-(B)|≤m-1,

则称D是非超欧拉有向图.

下面将介绍2个有向图D1和D2的强积有向图D1⊗D2成为超欧拉有向图的充分条件.

定理2.2令D1是超欧拉有向图且|V(D1)|≥2,D2是强连通有向迹的,则强积有向图D1⊗D2是超欧拉有向图.

证明令V(D1)={u1,u2,…,un1},V(D2)={v1,v2,…,vn2}且ui1=u1,vj1=v1.如果|V(D2)|=1,则D1⊗D2≅D1是超欧拉有向图.因此,假设|V(D2)|≥2.因为D1是超欧拉有向图,令H1是D1中弧数最少的生成有向闭迹且

H1=ui1ui2…uih1ui1, i1,i2,…,ih1∈[n1].(1)

因为D2是有向迹的,令H2是D2中从vj1到vjh2弧数最少的生成有向迹且

H2=vj1vj2…vjh2,j1,j2,…,jh2∈[n2].

(2)

根据(1)式有(uih1,ui1)∈A(D1).对于任意2个相邻的点vr-1,vr∈V(D2),2≤r≤n2,如果(vr-1,vr)∈A(D2),根据强积有向图的定义,则有

((uih1,vr-1),(ui1,vr))∈A(D1⊗D2).

(3)

因为D2是强连通的,所以D2包含一个最短(vjh2,vj1)-有向路P=vjskvjsk-1…vjs2vjs1,vjsk=vjh2且vjs1=vj1.

算法A

输出D1⊗D2中起点为(ui1,vj1)的生成有向闭迹H.

2) 如果p>q,令H:=H+((uih1,vjh2),(ui1,vjh2))∪P′,执行第5步.

3) 令H是当前的有向迹且终点为(uih1,vjr-1).

5) 返回有向迹H.

下面的例2.3介绍了一个超欧拉有向图和一个强连通但不是有向迹有向图,使得它们的强积有向图D1⊗D2是非超欧拉有向图.

例2.3令D1是超欧拉有向图,其点集为V(D1)={u1,u2},弧集为A(D1)={(u1,u2),(u2,u1)},则D1≅C2.令D2是强连通有向图,其点集为V(D2)={v1,v2,v3,v4,v5,v6,v7},弧集为A(D2)={(v2,v1),(v1,v3),(v3,v2),(v1,v4),(v4,v2),(v1,v5),(v5,v2),(v1,v6),(v6,v2),(v1v7),(v7,v2)}.因为D2不包含生成有向迹,所以D2不是有向迹有向图.根据定义1,可以得到D1和D2的强积有向图D1⊗D2(如图1所示).令B、B1、B2、B3、B4和B5是V(D1⊗D2)的点不交的子集,其中,B={(u1,v1),(u2,v1)},B1={(u1,v3),(u2,v3)},B2={(u1,v4),(u2,v4)},B3={(u1,v5),(u2,v5)},B4={(u1,v6),(u2,v6)}和B5={(u1,v7),(u2,v7)}.可以发现N-(Bi)⊆B,i∈[5]且|∂-(B)|=4.根据引理2.1,强积有向图D1⊗D2是非超欧拉有向图.

例2.3表明存在有向图D1,|V(D1)|=2和D2,|V(D2)|=7,则强积有向图D1⊗D2是非超欧拉有向图.事实上,对于n1,n2∈N,n2≤2n1+3,例2.3可以推广到一般的情况:令D1是一个有向圈,其点集为V(D1)={u1,u2,…,un1},D2是一个强连通有向图,其点集为V(D2)={v1,v2,…,vn2},弧集为A(D2)={(v2,v1),(v1,v3),(v3,v2),(v1,v4),(v4,v2),…,(v1,vn2),(vn2,v2)}.令B,B1,B2,…,Bn2-2是V(D1⊗D2)的点不交的子集,其中B={(u1,v1),(u2,v1),…,(un1,v1)},Bi={(u1,vi+2),(u2,vi+2),…,(un1,vi+2)},i∈[n2-2].可以发现N-(Bi)⊆B,i∈[n2-2]且|∂-(B)|=2n1≤n2-3=(n2-2)-1.根据引理2.1,强积有向图D1⊗D2是非超欧拉有向图,见图1,其中弧((u1,v1),(u2,vj)),((u2,v1),(u1,vj)),((u1,vj),(u2,v2))及((u2,vj),(u1,v2))被省略,j={3,4,5,6,7}.

图 1 有向图D1,D2和强积有向图D1⊗D2

下面的例2.4介绍了一个强连通有向迹有向图和一个强连通但不是有向迹有向图,使得它们的强积有向图D1⊗D2是非超欧拉有向图.

通过例2.3和例2.4可以说明定理1.2中的条件是最优的.

下面将介绍2个有向图D1和D2的强积有向图D1⊗D2成为双有向迹有向图的充分条件.

图2有向图D1和D2

Fig.2DigraphsofD1andD2

定理2.5令D1和D2是2个双有向迹有向图,则强积有向图D1⊗D2是双有向迹有向图.

证明令V(D1)={u1,u2,…,un1},V(D2)={v1,v2,…,vn2}.如果|V(D1)|=1,则D1⊗D2≅D2是双有向迹有向图.如果|V(D2)|=1,则D1⊗D2≅D1是双有向迹有向图.因此,假设|V(Di)|≥2,i=1,2.因为D1是双有向迹有向图,所以D1中存在一对不同的点x1,y1使得D1包含生成(x1,y1)-有向迹H11和生成(y1,x1)-有向迹H12,令

H11=usul1ul2…ulh1ut,

H12=utum1um2…umh1us,

(4)

x1=us,y1=ut,s,t,l1,l2,…,lh1,m1,m2,…,mh1∈[n1].令H11是D1中从us到ut弧数最少的生成有向迹,H12是D1中从ut到us弧数最少的生成有向迹.

类似地,因为D2是双有向迹有向图,所以D2中存在一对不同的点x2、y2使得D2包含生成(x2,y2)-有向迹H21和生成(y2,x2)-有向迹H22,令

H21=vi1vi2…vih2,H22=vj1vj2…vjh2,

(5)

x2=vi1=vjh2,y2=vih2=vj1,i1,i2,…,ih2,j1,j2,…,jh2∈[n2].令H21是D2中从vi1到vih2弧数最少的生成有向迹,H22是D2中从vj1到vjh2弧数最少的生成有向迹.

对于任意2个相邻的点vr-1,vr∈V(D2),2≤r≤n2,如果(vr-1,vr)∈A(D2),根据强积有向图的定义有

((us,vr-1),(us,vr))∈A(D1⊗D2),

((ut,vr-1),(ut,vr))∈A(D1⊗D2).

(6)

如果|V(D2)|是奇数,H1的终点为(ut,vih2),则可以利用上面的过程得到从点(ut,vj1)到点(us,vjh2)的生成有向迹H2;如果|V(D2)|是偶数,H1的终点为(us,vih2),则可以利用上面的过程得到从点(us,vj1)到点(us,vjh2)的生成有向迹H2.最终得到D1⊗D2中的生成(y,x)-有向迹H2.

算法B

输出D1⊗D2中起点为(us,vi1)的生成有向迹H1.

2) 如果p>q,执行第6步.

3) 令H1是当前的有向迹.

如果(ut,vir-1)为H1的终点,执行第4步.

如果(us,vir-1)为H1的终点,执行第5步.

6) 返回有向迹H1.

致谢新疆师范大学“十三五”校级重点学科数学招标课题(17SDKD1107)和新疆师范大学硕士研究生科技创新项目(XSY201602013)对本文给予了资助，谨致谢意.

[1] BONDY J A, MURTY U S R. Graph Theory[M]. New York:Springer-Verlag,2008.

[2] BANG-JENSEN J, GUTIN G. Digraphs:Theory Algorithms and Applications[M]. 2nd ed. New York:Springer-Verlag,2010.

[3] BOESCH F T, SUFFEL C, TINDELL R. The spanning subgraphs of Eulerian graphs[J]. J Graph Theory,1977,1(1):79-84.

[4] PULLEYBLANK W R. A note on graphs spanned by Eulerian graphs[J]. J Graph Theory,1979,3(3):309-310.

[5] CATLIN P A. Supereulerian graphs:a survey[J]. J Graph Theory,1992,16(2):177-196.

[6] CHEN Z H, LAI H J. Reduction techniques for super-Eulerian graphs and related topics:a survey[C]//Combinatorics and Graph Theory. New Jersey:World Science Citation Index Publishing,1995:53-69.

[7] LAI H J, SHAO Y, YAN H. An update on supereulerian graphs[J]. World Scientific and Engineering Academy Society Transactions on Mathematics,2013,12(9):926-940.

[8] GUTIN G. Cycles and paths in directed graphs[D]. Tel Aviv:Tel Aviv University,1993.

[9] GUTIN G. Connected (g;f)-factors and supereulerian digraphs[J]. Ars Combinatoria,2000,52:311-317.

[10] ALGEFARI M J, ALSATAMI K A, LAI H J, et al. Supereulerian digraphs with given local structures[J]. Information Processing Letters,2016,116(5):321-326.

[11] BANG-JENSEN J, MADDALONI A. Sufficient conditions for a digraph to be supereulerian[J]. J Graph Theory,2015,79(1):8-20.

[12] HONG Y, LAI H J, LIU Q. Supereulerian digraphs[J]. Discrete Mathematics,2014,330:87-95.

[13] GOULD R J. Advances on the Hamiltonian problem:a survey[J]. Graphs and Combinatorics,2003,19:7-52.

[14] DONG C, LIU J, ZHANG X, et al. Supereulerian digraphs with given diameter[J]. Appl Math Comput,2018,329:5-13.

[15] ALSATAMI K A, ZHANG X D, LIU J, et al. On a class of supereulerian digraphs[J]. Appl Math,2016,7(3):320-326.