關(guān)于l-路和圖的超歐拉性

李曉璞，劉 娟

(新疆師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，烏魯木齊 830017)

0 引 言

本文只考慮無(wú)向圖中沒(méi)有自環(huán)和重邊的簡(jiǎn)單圖，除非特別說(shuō)明，其他未給出的術(shù)語(yǔ)和定義可以參考文獻(xiàn)[1]和[2]。令圖G=VG,EG其中圖的點(diǎn)集為VG,圖的邊集為EG。在這篇文章中，我們用符號(hào)xy表示圖G中連接點(diǎn)x和點(diǎn)y的一條邊。符號(hào)a,b表示從a到b之間的所有整數(shù)。圖G中的道是一個(gè)交替序列W=v0e1v1e2…vl-1elvl，對(duì)于每一個(gè)i∈0,l,其中vi為點(diǎn)，ei為邊使得ei=vivi+1。如果v0=vl，則稱(chēng)W是一個(gè)閉道，否則是開(kāi)道。當(dāng)W的邊在上下文中已知時(shí)，可以記W為v0v1…vl。如果v0≠vl，則v0和vl是W的兩個(gè)端點(diǎn)，道的長(zhǎng)度是道中所含邊的條數(shù)。圖G中的一個(gè)跡是一個(gè)所有邊都不同的道。一個(gè)路是一個(gè)所有點(diǎn)都不同的道。路的長(zhǎng)度是路中所含邊的條數(shù)，長(zhǎng)度為l的路叫做l-路，它包含l+1個(gè)點(diǎn)。如果W中v0v1…vl是不同的點(diǎn)，l≥2，并且v0=vl，則稱(chēng)W是一個(gè)圈。如果對(duì)于圖G中每對(duì)不同的點(diǎn)x，y都存在連接x和y的路，則稱(chēng)G是連通圖。令G1和G2是兩個(gè)圖，如果VG1∩VG2=?,則稱(chēng)G1和G2是點(diǎn)不交的圖。如果EG1∩EG2=?,則稱(chēng)G1和G2是邊不交的圖。如果VH?VG,EH?EG并且EH中的每一條邊的兩個(gè)端點(diǎn)都在VH中，則稱(chēng)H是G的一個(gè)子圖。如果VH=VG，則稱(chēng)H是G的一個(gè)生成子圖。對(duì)于G中任意一個(gè)點(diǎn)v，用G-v表示從圖G中刪去點(diǎn)v及其所關(guān)聯(lián)的邊所得到的G的子圖，稱(chēng)為G的點(diǎn)刪除子圖。對(duì)于G中任意一條邊e，用G-e表示從圖G中刪去邊e所得到的G的子圖，稱(chēng)為G的邊刪除子圖。如果一個(gè)圖G包含一條閉跡使得EW=EG,則稱(chēng)G是歐拉圖。如果一個(gè)圖G包含一條閉跡使得VW=VG,或包含一個(gè)生成歐拉子圖，則稱(chēng)G是超歐拉圖。

定義1 在圖G中，如果對(duì)于每一個(gè)點(diǎn)v∈VG，滿足點(diǎn)刪除子圖G-v是超歐拉圖，那么G稱(chēng)為D-超歐拉圖。

定義2 在超歐拉圖G中，如果對(duì)于每一個(gè)點(diǎn)v∈VG，滿足點(diǎn)刪除子圖G-v是超歐拉圖，那么G稱(chēng)為T(mén)-超歐拉圖。

Boesch,Suffel和Tindell[3]在1977年提出了超歐拉問(wèn)題，他們致力于刻畫(huà)出包含生成歐拉子圖的無(wú)向圖，與此同時(shí)，他們表示這個(gè)問(wèn)題是極其困難的。Pulleyblank[4]在1979年證明了判定一個(gè)無(wú)向圖(甚至包含平面無(wú)向圖)是否是超歐拉的是NP-完全的。Catlin[5]在1988年提出了超歐拉圖的約化方法，是研究此類(lèi)問(wèn)題的重要工具。關(guān)于超歐拉問(wèn)題的研究方法，研究進(jìn)展及其應(yīng)用，參見(jiàn)文獻(xiàn)[6-9]。

在文獻(xiàn)[10]中，我們知道兩個(gè)超歐拉有向圖的2-和不一定是超歐拉有向圖。在文獻(xiàn)[11]中，介紹了有向圖中l(wèi)-路和的概念，并且給出了一些兩個(gè)有向圖的l-路和是超歐拉圖的充分條件。由這些結(jié)論，自然而然地想到了在無(wú)向圖中有關(guān)超歐拉圖的2-和與l-路和問(wèn)題。在本文中，我們將介紹兩個(gè)無(wú)向圖的2-和與l-路和是超歐拉圖、D-超歐拉圖和T-超歐拉圖的一些充分條件。

1 主要結(jié)論

首先，我們討論兩個(gè)無(wú)向圖的l-路和是超歐拉圖、D-超歐拉圖和T-超歐拉圖的一些充分條件。

定理1 設(shè)G1和G2是兩個(gè)點(diǎn)不交的超歐拉圖。在G1⊕l+1G2中，如果Gi有一個(gè)生成歐拉子圖Sii=1,2，使得ES1∩ES2=?。那么G1⊕l+1G2是超歐拉圖。

定理2 設(shè)G1和G2是兩個(gè)點(diǎn)不交的D-超歐拉圖。對(duì)于任意的點(diǎn)vi∈VGi，在G1⊕l+1G2中，如果Gi-vi有一個(gè)生成歐拉子圖SGi-vii=1,2，使得ESG1-v1∩ESG2-v2=?。那么G1⊕l+1G2是D-超歐拉圖。

情形1v=vj，?j∈0,l

如果v=vj，由D-超歐拉圖的定義，可知G1-vj是超歐拉圖，所以G1-vj有一個(gè)生成歐拉子圖，記作SG1-vj；同樣的，G2-vj是超歐拉圖，所以G2-vj有一個(gè)生成歐拉子圖，記作SG2-vj，并且ESG1-vj∩ESG2-vj=?，那么SG1-vj∪SG2-vj是G1⊕l+1G2-vj的一個(gè)生成歐拉子圖。即G1⊕l+1G2是D-超歐拉圖。

情形2v∈VG1⊕l+1G2vj,?j∈0,l

如果v∈VG1vj，由D-超歐拉圖的定義，可知G1-v是超歐拉圖，所以G1-v有一個(gè)生成歐拉子圖，記作SG1-v；同樣的，G2-v0是超歐拉圖，所以G2-v0有一個(gè)生成歐拉子圖，記作SG2-v0，并且ESG1-v∩ESG2-v0=?，那么SG1-v∪SG2-v0是G1⊕l+1G2-v的一個(gè)生成歐拉子圖。如果v∈VG2vj,由D-超歐拉圖的定義，可知G2-v是超歐拉圖，所以G2-v有一個(gè)生成歐拉子圖，記作SG2-v；同樣的，G1-v0是超歐拉圖，所以G1-v0有一個(gè)生成歐拉子圖，記作SG1-v0，并且ESG2-v∩ESG1-v0=?，那么SG2-v∪SG1-v0是G1⊕l+1G2-v的一個(gè)生成歐拉子圖。即G1⊕l+1G2是D-超歐拉圖。

定理3 設(shè)G1和G2是兩個(gè)點(diǎn)不交的圖。G1是一個(gè)T-超歐拉圖，G2是一個(gè)D-超歐拉圖。在G1⊕l+1G2中，如果G1有一個(gè)生成歐拉子圖SG1，對(duì)于任意點(diǎn)v2∈VG2，G2-v2有一個(gè)生成歐拉子圖SG2-v2，使得ESG1∩ESG2-v2=?。那么G1⊕l+1G2是T-超歐拉圖。

由T-超歐拉的定義，可知G1是超歐拉圖，所以G1有一個(gè)生成歐拉子圖，記作SG1。由D-超歐拉的定義，可知G2-v0是超歐拉圖，所以G2-v0有一個(gè)生成歐拉子圖，記作SG2-v0。并且ESG1∩ESG2-v0=?，所以SG1∪SG2-v0是G1⊕l+1G2的一個(gè)生成歐拉子圖，即G1⊕l+1G2是超歐拉圖。

對(duì)于任意點(diǎn)v∈VG1⊕l+1G2，需證明任意點(diǎn)刪除子圖G1⊕l+1G2-v是超歐拉圖，我們分以下兩種情形討論：

情形1v=vj，?j∈0,l

如果v=vj，由T-超歐拉圖的定義，可知G1-vj是超歐拉圖，所以G1-vj有一個(gè)生成歐拉子圖，記作SG1-vj；由D-超歐拉圖的定義，可知G2-vj是超歐拉圖，所以G2-vj有一個(gè)生成歐拉子圖，記作SG2-vj，并且ESG1-vj∩ESG2-vj=?，那么SG1-vj∪SG2-vj是G1⊕l+1G2-vj的一個(gè)生成歐拉子圖。即G1⊕l+1G2是T-超歐拉圖。

情形2v∈VG1⊕l+1G2vj，?j∈0,l

如果v∈VG1vj，由T-超歐拉圖的定義，可知G1-v是超歐拉圖，所以G1-v有一個(gè)生成歐拉子圖，記作SG1-v；由D-超歐拉圖的定義，可知G2-v0是超歐拉圖，所以G2-v0有一個(gè)生成歐拉子圖，記作SG2-v0，并且ESG1-v∩ESG2-v0=?，那么SG1-v∪SG2-v0是G1⊕l+1G2-v的一個(gè)生成歐拉子圖。如果v∈VG2vj，由D-超歐拉圖的定義，可知G2-v是超歐拉圖，所以G2-v有一個(gè)生成歐拉子圖，記作SG2-v；由T-超歐拉圖的定義，可知G1是超歐拉圖，所以G1有一個(gè)生成歐拉子圖，記作SG1，并且ESG1∩ESG2-v=?，那么SG1∪SG2-v是G1⊕l+1G2-v的一個(gè)生成歐拉子圖。即G1⊕l+1G2是T-超歐拉圖。

以上我們討論了兩個(gè)無(wú)向圖的l-路和是超歐拉圖、D-超歐拉圖和T-超歐拉圖的一些充分條件。

特別的，以下我們將討論兩個(gè)無(wú)向圖的2-和是超歐拉圖、D-超歐拉圖和T-超歐拉圖的一些更優(yōu)的充分條件。

定理4 設(shè)G1和G2是兩個(gè)點(diǎn)不交的超歐拉圖，那么G1⊕2G2是超歐拉圖。

證明因?yàn)镚1和G2是超歐拉圖，即Gi有一個(gè)生成歐拉子圖Sii=1,2。由G1⊕2G2的定義可知，如果ES1∩ES2≠?,令ES1∩ES2=e，那么S1∪S2-e是G1⊕2G2的一個(gè)生成歐拉子圖；如果ES1∩ES2=?，那么S1∪S2是G1⊕2G2的一個(gè)生成歐拉子圖，即G1⊕2G2是超歐拉圖。

定理5 設(shè)G1和G2是兩個(gè)點(diǎn)不交的D-超歐拉圖，那么G1⊕2G2是D-超歐拉圖。

證明設(shè)e1=v11v12∈EG1和e2=v21v22∈EG2是兩條不相交的邊。由G1⊕2G2的定義，令v11=v21=v1，v12=v22=v2。對(duì)于任意點(diǎn)v∈VG1⊕2G2，需證明任意點(diǎn)刪除子圖G1⊕2G2-v是超歐拉圖，我們分以下兩種情形討論：

情形1v=v1或v=v2

如果v=v1，由D-超歐拉圖的定義，可知G1-v1是超歐拉圖，所以G1-v1有一個(gè)生成歐拉子圖，記作SG1-v1；同樣的，G2-v1是超歐拉圖，所以G2-v1有一個(gè)生成歐拉子圖，記作SG2-v1，那么SG1-v1∪SG2-v1是G1⊕2G2-v1的一個(gè)生成歐拉子圖。如果v=v2，由D-超歐拉圖的定義，可知G1-v2是超歐拉圖，所以G1-v2有一個(gè)生成歐拉子圖，記作SG1-v2；同樣的，G2-v2是超歐拉圖，所以G2-v2有一個(gè)生成歐拉子圖，記作SG2-v2，那么SG1-v2∪SG2-v2是G1⊕2G2-v2的一個(gè)生成歐拉子圖。即G1⊕2G2是D-超歐拉圖。

情形2v∈VG1⊕2G2v1,v2

如果v∈VG1v1,v2，由D-超歐拉圖的定義，可知G1-v是超歐拉圖，所以G1-v有一個(gè)生成歐拉子圖，記作SG1-v；同樣的，G2-v1是超歐拉圖，所以G2-v1有一個(gè)生成歐拉子圖，記作SG2-v1，那么SG1-v∪SG2-v1是G1⊕2G2-v的一個(gè)生成歐拉子圖。如果v∈VG2v1,v2，由D-超歐拉圖的定義，可知G2-v是超歐拉圖，所以G2-v有一個(gè)生成歐拉子圖，記作SG2-v；同樣的，G1-v1是超歐拉圖，所以G1-v1有一個(gè)生成歐拉子圖，記作SG1-v1，那么SG2-v∪SG1-v1是G1⊕2G2-v的一個(gè)生成歐拉子圖。即G1⊕2G2是D-超歐拉圖。

定理6 設(shè)G1和G2是兩個(gè)點(diǎn)不交的圖。G1是一個(gè)T-超歐拉圖，G2是一個(gè)D-超歐拉圖。那么G1⊕2G2是T-超歐拉圖。

證明設(shè)e1=v11v12∈EG1和e2=v21v22∈EG2是兩條不相交的邊。由G1⊕2G2的定義，令v11=v21=v1，v12=v22=v2。

由T-超歐拉的定義，可知G1是超歐拉圖，所以G1有一個(gè)生成歐拉子圖，記作SG1。由D-超歐拉的定義，可知G2-v1是超歐拉圖，所以G2-v1有一個(gè)生成歐拉子圖，記作SG2-v1，所以SG1∪SG2-v1是G1⊕2G2的一個(gè)生成歐拉子圖，即G1⊕2G2是超歐拉圖。

對(duì)于任意點(diǎn)v∈VG1⊕2G2，需證明任意點(diǎn)刪除子圖G1⊕2G2-v是超歐拉圖，我們分以下兩種情形討論：

情形1v=v1或v=v2

如果v=v1，由T-超歐拉圖的定義，可知G1-v1是超歐拉圖，所以G1-v1有一個(gè)生成歐拉子圖，記作SG1-v1；由D-超歐拉圖的定義，可知G2-v1是超歐拉圖，所以G2-v1有一個(gè)生成歐拉子圖，記作SG2-v1，那么SG1-v1∪SG2-v1是G1⊕2G2-v1的一個(gè)生成歐拉子圖。如果v=v2，由T-超歐拉圖的定義，可知G1-v2是超歐拉圖，所以G1-v2有一個(gè)生成歐拉子圖，記作SG1-v2；由D-超歐拉圖的定義，可知G2-v2是超歐拉圖，所以G2-v2有一個(gè)生成歐拉子圖，記作SG2-v2，那么SG1-v2∪SG2-v2是G1⊕2G2-v2的一個(gè)生成歐拉子圖。即G1⊕2G2是T-超歐拉圖。

情形2v∈VG1⊕2G2v1,v2

如果v∈VG1v1,v2，由T-超歐拉圖的定義，可知G1-v是超歐拉圖，所以G1-v有一個(gè)生成歐拉子圖，記作SG1-v；由D-超歐拉圖的定義，可知G2-v1是超歐拉圖，所以G2-v1有一個(gè)生成歐拉子圖，記作SG2-v1，那么SG1-v∪SG2-v1是G1⊕2G2-v的一個(gè)生成歐拉子圖。如果v∈VG2v1,v2，由D-超歐拉圖的定義，可知G2-v是超歐拉圖，所以G2-v有一個(gè)生成歐拉子圖，記作SG2-v；由T-超歐拉圖的定義，可知G1是超歐拉圖，所以G1有一個(gè)生成歐拉子圖，記作SG1，那么SG2-v∪SG1是G1⊕2G2-v的一個(gè)生成歐拉子圖。即G1⊕2G2是T-超歐拉圖。

2 總 結(jié)

超歐拉問(wèn)題的研究是一個(gè)比較新的研究領(lǐng)域，具有很廣闊的研究前景。本文類(lèi)比出了無(wú)向圖中l(wèi)-路和及2-和的概念，并且給出了在無(wú)向圖中D-超歐拉圖和T-超歐拉圖的定義，通過(guò)進(jìn)行運(yùn)算及討論探究得到了一系列關(guān)于超歐拉的充分條件。本文是從無(wú)向圖的角度，探究關(guān)于超歐拉圖的l-路和及2-和運(yùn)算之后的結(jié)論。我們還可以從有向圖的角度可慮這個(gè)問(wèn)題，看看在有向圖的條件下，是否可以探究出關(guān)于超歐拉有向圖的一些結(jié)論。也可以考慮在無(wú)向、有向的條件下，對(duì)于D-超歐拉圖和T-超歐拉圖進(jìn)行其它的運(yùn)算，能否得到一些結(jié)論，這些都是值得我們繼續(xù)討論和探究的問(wèn)題。