關于超歐拉的冪有向圖

崔秋月，劉 娟

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

關于超歐拉的冪有向圖

崔秋月，劉 娟*

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

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

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

1 預備知識

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

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

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

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

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

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

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

2 主要結果

命題1[1]一個有向圖D的直徑是有限的當且僅當D是強連通的。

定理1 設D是一個強連通有向圖且diam（D）=d，則D的d次冪有向圖是完全有向圖。

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

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

證明 我們想要在D的平方圖中構造一個生成有向閉跡S。因為│（Si，Sj）D│=1當且僅當j=i+1，j是以 n為模的，1≤i≤n，1≤j≤n+1，所以任意的 Si中存在一個點的出度為2，一個點的入度為2，不妨假設即D中存在弧設任意的其中

下面討論w的奇偶性:

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

證明 因為 Γ=｛S1，S2，…，Sn｝是 D 中的有向圈的集合且滿足V（D）=Usi∈ΓV（S）i，所以，如果n=1，則D是超歐拉有向圖，D的平方圖也是超歐拉有向圖。因此,假設不存在這種情況。如果n≥2，因為對任意的1≤i＜j≤n，Si和Sj恰有一段公共弧且只存在于Si和 Sj中當且僅當 j=i+1, 所以設 Si：xu1u2…usp0p1p2…pkx和Sj:xv1v2…vtp0p1p2…pkx是n個有向圈中任意兩個相鄰的恰有一段公共弧的有向圈且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。

下面對k的范圍進行分類討論:

若 k=0，有向路 P1：xu1u2…usp0，有向路 P2：v1v2…vtp0。因為D中有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 的平方圖中關于 si和 sj的一個生成有向閉跡。因為si和sj是n個有向圈中的任意兩個相鄰的恰有一段公共弧的有向圈，且公共弧只存在于si和sj中，所以D的平方圖中一定包含一個生成有向閉跡。故D的平方圖是超歐拉有向圖。

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

當k為奇數(shù)時,因為在 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 的平方圖中關于 si和 sj的一個生成有向閉跡。同理，D的平方圖中一定包含一個生成有向閉跡。故D的平方圖是超歐拉有向圖。

當k為偶數(shù)時，因為D中有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 的平方圖中關于 si和 sj的一個生成有向閉跡。同理，D的平方圖中一定包含一個生成有向閉跡。故D的平方圖是超歐拉有向圖。

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

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

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

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

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

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

當 s=1,即 x1=xs。因為 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

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

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

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