關(guān)于超歐拉的冪有向圖

崔秋月，劉 娟

(新疆師范大學(xué)，新疆 烏魯木齊 830017)

關(guān)于超歐拉的冪有向圖

崔秋月，劉 娟*

(新疆師范大學(xué)，新疆 烏魯木齊 830017)

如果一個(gè)有向圖D包含一個(gè)生成有向閉跡，則稱D是超歐拉有向圖。研究關(guān)于一個(gè)強(qiáng)連通有向圖或一個(gè)強(qiáng)連通的有向圖類，使之在經(jīng)過p次冪有向圖的運(yùn)算后成為超歐拉有向圖的充分條件：有向圖D包含一個(gè)有向圈的集合 Γ=｛S1，S1，…，Sn｝且滿足 V（D）=Usi∈ΓV(Si)，D 的平方圖是超歐拉有向圖的充分條件。對(duì)于s,t圖類中的強(qiáng)連通有向圖，當(dāng)s是奇數(shù)時(shí)，則對(duì)于任意的是超歐拉有向圖；當(dāng)s是偶數(shù)時(shí)，則對(duì)于任意的是超歐拉有向圖。

超歐拉有向圖；p次冪有向圖；平方圖；歐拉有向圖

1 預(yù)備知識(shí)

本文只考慮沒有自環(huán) (一條弧的兩個(gè)端點(diǎn)為同一個(gè)點(diǎn))和平行弧(兩個(gè)點(diǎn)之間有兩條方向相同的弧)的簡單有向圖。沒有被定義的術(shù)語和符號(hào)在文獻(xiàn)[1]中可以參考。令 D=（V（D），A（D））是簡單有向圖,其中有向圖D的點(diǎn)集為V（D），弧集為A（D）。在本文中，我們用符號(hào)（u，v）表示有向圖中從點(diǎn)u到點(diǎn)v的一條弧。對(duì)于一個(gè)整數(shù) n，定義［n］=｛1，2，…，n｝。有向圖D中的一個(gè)道是一個(gè)交替序列W=x1a1x2a2x3…xk-1ak-1xk，其中 xi為點(diǎn)，aj為弧使得 aj=（xj，xj+1）,對(duì)于每一個(gè) i∈[k]，j∈[k-1]，則稱 W 是一個(gè)從 x1到 xk的道或者是一個(gè)（x1，xk）-道。如果 x1=xk，則稱 W 是一個(gè)閉道，否則是開道。當(dāng)W的弧在文章中已被理解時(shí)，可以記W為x1x2…xk。如果x1≠xk，則點(diǎn)x1是W的起點(diǎn)，點(diǎn)xk是W的終點(diǎn)，x1和xk是W的端點(diǎn)。道的長度是它的弧的條數(shù)。有向圖D中的一個(gè)有向跡是一個(gè)所有弧都不同的道；一個(gè)有向路是一個(gè)所有點(diǎn)都不同的道。如果 W 中 x1，x2，…，xk-1是不同的點(diǎn)，k≥2且x1=xk，則稱W是一個(gè)有向圈。如果對(duì)于有向圖D中每對(duì)不同的點(diǎn)x，y都存在一個(gè)（x，y）-道和一個(gè)（y，x）-道,則稱 D 是強(qiáng)連通的。令 W=x1x2…xk，Q=y1y2…yt是有向圖D中的一對(duì)道，如果V（W）∩V（Q）= ? ，則稱W和Q是點(diǎn)不交的；如果A（W）∩A（Q）= ? ，則稱W和Q是弧不交的。如果V（H）? V（D），A（H）?A（D）并且A（H）中的每一條弧的兩個(gè)端點(diǎn)都在V（H）中，則稱H是D的一個(gè)子圖。如果V（H）=V（D），則 稱H是D的一個(gè)生成子圖。如果A（D）中每一條弧都在A（H）中，每一條弧的兩個(gè)端點(diǎn)都在V（H）中，則稱 H 是由 X=V（H）誘導(dǎo)的，記作 H=D〈X〉并稱H是D的一個(gè)誘導(dǎo)子圖。如果H是D的一個(gè)子圖且 S ? A（D）-A（H），V（D〈S〉）? V（H），則稱H+S是D的子圖，其點(diǎn)集為V（H），弧集為A（H）+S。我們一般用D-a代替 D-｛a｝，用 D+a代替 D+｛a｝。令D1和D2是兩個(gè)不交的有向圖，D1與D2的并記作D1∪D2，它的點(diǎn)集為 V（D1∪D2）=V（D1）∪V（D2）,弧集為 A（D1∪D2）=A（D1）∪A（D2）。對(duì)于 X，Y ? V（D），定義（X，Y）D=｛（x，y）∈A（D）：x∈X，y∈Y｝。當(dāng) Y=V（D）-X 時(shí)，定義 ?+D（ X）=（X，V（D）-X）D和 ??（DX）=（V（D）-X，X）D。對(duì)于一個(gè)點(diǎn) v∈V（D），是D中點(diǎn)v的出度，是D中點(diǎn)v的入度。如果x，y是D中的兩個(gè)點(diǎn)且x到y(tǒng)是可達(dá)的,則在D中從x到y(tǒng)的距離記作dis（tx，y），是（x，y）-道的最小長度,否則dis（tx，y）=∞。D中的一個(gè)點(diǎn)集X到另一個(gè)點(diǎn)集Y的距離為dis（tX，Y）=max｛dis（tx，y），x∈X，y∈Y｝。有向圖D的直徑為diam（D）=dis（tV，V），即diam（D）=max｛dis（tV，V），x∈V，y∈V｝。我們定義,如果有向圖D中只有一個(gè)點(diǎn)，則diam（D）=0。如果D不是強(qiáng)連通有向圖，即存在兩個(gè)點(diǎn)x，y使得dis（tx，y）=∞，則diam（x，y）=∞。如果對(duì)于有向圖D中任意一對(duì)不同的點(diǎn) x，y，既存在（x，y），又存在(y，x)，則稱D為完全有向圖。

下面介紹p次冪有向圖的定義。

定義1[1]對(duì)于一個(gè)正整數(shù)p和一個(gè)有向圖D，p次冪有向圖 D 定義如下:V（D ）=V（D）,如果x≠y且有dis（tx，y）≤p，則有（x，y）∈A（D）。

根據(jù)以上的定義易知D1=D。當(dāng)p=2時(shí),稱D2為D的平方圖。當(dāng)p=3時(shí)，稱D3為D的立方圖。

如果D不是強(qiáng)連通有向圖,則p次冪有向圖不是強(qiáng)連通的且不可能包含一個(gè)生成閉有向跡。因此，以下所有的有向圖都假設(shè)是強(qiáng)連通的。

Boesch，Suffel和 Tindell[2]在 1977 年提出了超歐拉問題,他們致力于刻畫出包含生成歐拉子圖的無向圖，同時(shí)他們表示這個(gè)問題是非常困難的。Pulleyblank[3]在1979年證明了判定一個(gè)無向圖(甚至包含平面無向圖)是否是超歐拉的是NP-complete。截至今日，已經(jīng)有大量關(guān)于超歐拉無向圖的研究，例如文獻(xiàn)[4-6]。

因此，在超歐拉無向圖的基礎(chǔ)上，超歐拉有向圖很快便被廣泛的研究。如果一個(gè)有向圖D包含一個(gè)有向閉跡W使得A（W）=A（D），則稱D是歐拉有向圖。如果一個(gè)有向圖D包含一個(gè)有向閉跡W使得V（W）=V（D）或包含一個(gè)生成歐拉子圖,則稱D是超歐拉有向圖。否則，稱D是非超歐拉有向圖。如今,最主要的問題就是判定一個(gè)有向圖是超歐拉有向圖。Gutin[7，8]進(jìn)行了早期的研究。一些近期的發(fā)展可以參考文獻(xiàn)[9，10]。

2 主要結(jié)果

命題1[1]一個(gè)有向圖D的直徑是有限的當(dāng)且僅當(dāng)D是強(qiáng)連通的。

定理1 設(shè)D是一個(gè)強(qiáng)連通有向圖且diam（D）=d，則D的d次冪有向圖是完全有向圖。

證明 設(shè) V（D）=｛v1，v2，…，vn｝并且對(duì)于 D 中的任意兩個(gè)不同的點(diǎn) vi和 vj，i≠j且 i，j∈[n]。根據(jù) p次冪有向圖的定義,可以得出V（Dd）=V(D)。因?yàn)镈是一個(gè)強(qiáng)連通有向圖且diam（D）=d，則D中有dist（vi，vj）≤diam(D)=d，所以對(duì)于有向圖Dd中任意兩個(gè)不同的點(diǎn)vi和vj都存在（vi，vj）和(vj，vi)，因此，有向圖Dd是完全有向圖。

定理 2 設(shè) Γ=｛S1，S2，…，Sn｝是有向圖 D 中的有向圈的集合并且V（D）=Usi∈ΓV（Si）。如果滿足對(duì)任意的1≤i≤n，1≤j≤n+1，│（Si，Sj）D│=1當(dāng)且僅當(dāng)j=i+1，j是以n為模的,則D的平方圖是超歐拉有向圖。

證明 我們想要在D的平方圖中構(gòu)造一個(gè)生成有向閉跡S。因?yàn)椹Γ⊿i，Sj）D│=1當(dāng)且僅當(dāng)j=i+1，j是以 n為模的，1≤i≤n，1≤j≤n+1，所以任意的 Si中存在一個(gè)點(diǎn)的出度為2，一個(gè)點(diǎn)的入度為2，不妨假設(shè)即D中存在弧設(shè)任意的其中

下面討論w的奇偶性:

定理 3 設(shè) Γ=｛S1，S2，…，Sn｝是有向圖 D 中的有向圈的集合并且V（D）=Usi∈ΓV（S）i。如果滿足對(duì)任意的 1≤i＜j≤n，Si和 Sj恰有一段公共弧且只存在于Si和Sj中當(dāng)且僅當(dāng)j=i+1，則D的平方圖是超歐拉有向圖。

證明 因?yàn)?Γ=｛S1，S2，…，Sn｝是 D 中的有向圈的集合且滿足V（D）=Usi∈ΓV（S）i，所以，如果n=1，則D是超歐拉有向圖，D的平方圖也是超歐拉有向圖。因此,假設(shè)不存在這種情況。如果n≥2，因?yàn)閷?duì)任意的1≤i＜j≤n，Si和Sj恰有一段公共弧且只存在于Si和 Sj中當(dāng)且僅當(dāng) j=i+1, 所以設(shè) Si：xu1u2…usp0p1p2…pkx和Sj:xv1v2…vtp0p1p2…pkx是n個(gè)有向圈中任意兩個(gè)相鄰的恰有一段公共弧的有向圈且x，u1，u2，…，us，v1，v2，…，vt，p0，p1，p2，…，pk∈V（D）。根據(jù) p 次冪有向圖的定義容易得到V（D2）=V（D），并且在D的平方圖中存在有向路P1：xu1u2…usp0p1p2…pk和有向路 P2：v1v2…vtp0。

下面對(duì)k的范圍進(jìn)行分類討論:

若 k=0，有向路 P1：xu1u2…usp0，有向路 P2：v1v2…vtp0。因?yàn)镈中有dis（tp0，v1）≤2，dis（tp0，x）≤2，所以有（p0，v1）∈A（D2）和（p0，x）∈A（D2）。因此S（i，）j=P1+（p0，v1）+p2+（p0，x）是 D 的平方圖中關(guān)于 si和 sj的一個(gè)生成有向閉跡。因?yàn)閟i和sj是n個(gè)有向圈中的任意兩個(gè)相鄰的恰有一段公共弧的有向圈，且公共弧只存在于si和sj中，所以D的平方圖中一定包含一個(gè)生成有向閉跡。故D的平方圖是超歐拉有向圖。

若 k≥1，因?yàn)?D 中有 dist(pk，v1)≤2，所以 D 的平方圖中存在(pk，v1)。

當(dāng)k為奇數(shù)時(shí),因?yàn)樵?D中有 dist（p0，p2）=dist（p2，p4）=…=dist（pk-3，pk-1）=dist（pk-1，x）=2,所以D的平方圖中存在有向路P3：p0p2p4…pk-3pk-1x。因此S（i，j）=P1+（pk，v1）+P2∪P3是 D 的平方圖中關(guān)于 si和 sj的一個(gè)生成有向閉跡。同理，D的平方圖中一定包含一個(gè)生成有向閉跡。故D的平方圖是超歐拉有向圖。

當(dāng)k為偶數(shù)時(shí)，因?yàn)镈中有dist（p0，p2）=dist（p2，p4）=…=dist（pk-2，pk）=2且dist（pk，x）＜2,所以D的平方圖中存在有向路 P4:p0p2p4…pk-2pkx。因此，S（i，i+1）=P1+（pk，v1）+P2∪P4是 D 的平方圖中關(guān)于 si和 sj的一個(gè)生成有向閉跡。同理，D的平方圖中一定包含一個(gè)生成有向閉跡。故D的平方圖是超歐拉有向圖。

下面介紹的引理1將被應(yīng)用在證明一個(gè)有向圖是非超歐拉有向圖的例子中。

引理1[10]對(duì)于某個(gè)正整數(shù)m和一個(gè)有向圖D，如果 V（D）中包含點(diǎn)不交的子集 B1，B2，…，Bm且滿足以下兩個(gè)條件，則稱D是非超歐拉有向圖:

（1）N-（Bi）Bi∈[m]；

設(shè)Fs，t（s，t≥1且滿足n=s+t）是一個(gè)n個(gè)點(diǎn)的強(qiáng)連通有向圖,它是通過將一條有向路x1x2…xs加上含有t個(gè)新點(diǎn)的集合Y（t），并且連接xs到每一個(gè)新點(diǎn),連接 Y（t）中的每一個(gè)點(diǎn)到 x1。令s，t為一個(gè)有向圖 D的集族，此集族是通過將有向圖Fs，t加上形如（xl，xk），1≤k＜l≤s的弧得到的。

若 t=1，即 y1=yt。因?yàn)?D∈s，t，所以無論 S 取何值都有S:x1x2…xsy1x1是D中的生成有向閉跡，則D是超歐拉有向圖。

若t≥2,下面討論s的取值范圍:

當(dāng) s=1,即 x1=xs。因?yàn)?D∈s，t，所以 D 中存在（x1，y1）（,y1，x1），（x1，y2），（y2，x1），…，（x1，y）t，（yt，x1）。因此，S=（x1，y1）+（y1，x1）+（x1，y2）+（y2，x1）+…+（x1，y）t+（yt，x1）是D中的生成有向閉跡，則D是超歐拉有向圖。

下面討論s的奇偶性:

y1y2yt圈。因此中的生成有向閉跡，則是超歐拉有向圖。

例1說明了定理4中的條件是最優(yōu)的。

［1］J.Bang-Jensen and G.Gutin.Digraphs:Theory［M］.Algorithms and Applications，Second Edition，Springer，2010.

［2］F.T.Boesch，C.Suffel，and R.Tindell.The spanning subgraphs of eulerian graphs［J］.Journal of Graph Theory，1977，（1）：79-84.

［3］W.R.Pulleyblank.A note on graphs spanned by Eulerian graphs［J］.Journal of Graph Theory，1979，（3）：309-310.

［4］P.A.Catlin.Supereuleriangraphs:asurvey［J］.JournalofGraph Theory，1992，（16）：177-196.

［5］Z.H.Chen,H.J.Lai.Reduction techniques for super-Eulerian graphsandrelatedtopics-asurvey［A］.Combinatoricsand graphtheory'95，Volume1（Hefei），WorldScienceCitation Index Publishing，River Edge，NJ（1995）：53-69.

［6］H.J.Lai，Y.Shao，and H.Yan.An update on supereulerian Graphs［J］.World Scientific and Engineering Academy and Society Transactions on Mathematics，2013，12（9）：926-940.

［7］G.Gutin.Cycles and paths in directed graphs［D］.Tel A－viv-Yafo：Tel Aviv University，1993.

［8］G.Gutin.Connected（g；f）-factors and supereulerian digraphs［J］.Ars Combinatoria，2000，（54）:311-317.

［9］M.J.Algefari，K.A.Alsatami，H.J.Lai and J.Liu.Supereulerian digraphs with given local structures［J］.Information Processing Letters，2016，116（5）：321-326.

［10］K.A.Alsatami,X.D.Zhang，J.Liu and H.J.Lai.On a class of supereulerian digraphs［J］.Applied Mathematics，2016，（7）：320-326.

On Supereulerian Powers of Digraphs

CUI Qiu-yue，LIU Juan*
(Xinjiang Normal University，Urumqi 830017，China)

Adigraph D is supereulerian if contains a spanning closed ditrail.In this paper,we will give the sufficient conditions on a strong digraph or a strong digraph family isobtained for the pthpower of them to be supereulerian：let a digraph has a set of dicycle Γ=｛ S1，S1，…，Sn｝and V（D）=Usi∈ΓV(Si)，the sufficient conditions on its square digraph is supereulerian.For every D∈s，t，ifsis odd，then for everyis supereulerian.Ifsis even，then for everyDDis supereulerian.

supereulerian digraph；pthpower；square digraph；eulerian digraph

O157.5

A

1674-3229（2017）03-0015-05

2017-03-12

國家自然科學(xué)基金(61363020,11301450);新疆師范大學(xué)研究生科技創(chuàng)新基金資助項(xiàng)目(XSY201602010)

崔秋月(1992-)，女，新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院碩士研究生，研究方向：圖論及其應(yīng)用。

劉娟(1981-)，女，博士，新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院教授，研究方向：圖論及其應(yīng)用。