牛兆宏，馮雅瓊，王劉巖

（山西大學 數(shù)學科學學院，山西 太原 030006）

0 引言

本文只考慮有限無環(huán)的圖和有向圖，沒有特殊說明的話，圖指的是無向圖。文中未定義的符號和術語，無向圖參見文獻［1］，有向圖參見文獻［2］。

定理1[9]設G是n個頂點的連通圖。如果G∈F，那么對于任意的 α∈Sn，α(G)都是超歐拉圖。

一個有向圖稱為是歐拉有向圖，是指它有一條包含所有弧的閉跡。如果一個有向圖D包含一個生成歐拉子有向圖，則稱D是超歐拉有向圖。文獻［15］和［16］給出了若干有向圖是超歐拉圖的充分條件。

受到廣義棱柱較多的研究成果及應用、以及有向圖的超歐拉性的相關研究的啟發(fā)，本文主要討論兩個有向圖的廣義棱柱的超歐拉性質。我們將無向圖G的廣義棱柱的概念推廣到有向圖上，給出了如下定義（最后一節(jié)將指出這一定義與圖G的α-廣義棱柱α(G)的聯(lián)系）。設D和H是兩個有向圖，記

下文中，第1節(jié)介紹與置換α有關的記號，并且給出一個判斷廣義棱柱的超歐拉性質的引理。第2節(jié)證明了兩個超歐拉有向圖的廣義棱柱一定是超歐拉有向圖，并且利用上一節(jié)的引理給出了一類由有向可跡圖和超歐拉有向圖所構造的廣義棱柱是超歐拉有向圖的一個特征刻畫。作為主要結果的推論，最后一節(jié)討論了無向圖的廣義棱柱的超歐拉性質。

1 預備知識

對每個有向圖D，對應的有一個無向圖G，它的頂點集與D相同，且對D的每條弧，G中有一條對應邊與它有相同的端點。稱G為有向圖D的基礎圖。如果一個有向圖D的基礎圖是連通的，則稱D是連通的。如果對于任意一對頂點x，y∈V(D)，D中都存在從x到y(tǒng)的有向路和y到x的有向路，則稱D是強連通的。下面的定理是有向圖版本的歐拉定理。

設α∈Sn是一個置換，并且設α是r個輪換的乘積B1B2…Br。在不引起混淆的前提下，Bi表示α中的某個輪換，也表示該輪換中所含元素構成的集合。為了證明過程中表述方便，引入如下的符號和術語。在α的每一個輪換Bi中，記ci=min(Bi)和fi=max(Bi)，并且在表示輪換Bi時，總是約定最小元位于該輪換的第1個位置，同時將該輪換簡記作 Bi=(ci…fi…)。若 ci=fi，則 Bi=(ci)。在將置換α表示成輪換之積時，按照每個輪換中最小元從小到大的次序排列這些輪換。這時，我們將置換α表示為

下面給出一個判斷廣義棱柱是超歐拉有向圖的引理。

引理3 設P是一條n個頂點的有向路，H是超歐拉有向圖，α=B1B2…Br∈Sn是一個置換。如果存在一個輪換Bl∈α，使得對于α中其他任意一個輪換Bi，cl

因為H是超歐拉有向圖，所以它有一個生成歐拉子有向圖S′。注意到任意一個歐拉有向圖都可以分解為一些弧不交的有向圈。我們將S′分解出的弧不交的有向圈記為C1，C2，…，Cm。不妨設C1=u1u2…un1u1。

在A(S)中，我們記弧子集

綜上所述，引理得證。

2 有向廣義棱柱的超歐拉性質

本節(jié)討論兩個有向圖的廣義棱柱的超歐拉性質。

定理4 設D和H是超歐拉有向圖，|V(D)|=n，那么對于任意的α∈Sn，D對H的α-廣義棱柱αH(D)是超歐拉有向圖。

下面利用引理3，給出了P是有向路，H是超歐拉有向圖，并且在α中所含輪換個數(shù)r≤3時，αH(P)是超歐拉有向圖的一個特征刻畫。

定理5 設P是一條n個頂點的有向路，H是超歐拉有向圖，α=B1B2…Br∈Sn是一個置換。如果r≤3，那么P對H的α-廣義棱柱αH(P)是超歐拉有向圖當且僅當α連通。

證明 首先證明充分性。我們斷言在定理5的條件下，對于Sn中的任意一個置換α=B1B2…Br，一定存在一個輪換Bl∈α，使得對于α中其他任意一個輪換Bi，cl

若r=1，置換α中只含一個輪換B1，顯然斷言成立。若r=2，即α=B1B2，取Bl=B1，由于α是連通的，所以c1f1，由于α是連通的，取Bl=B2，可知c2

由該斷言和引理3可知，αH(P)是超歐拉有向圖。充分性得證。

這就證明了定理5。

如果有向圖D包含一條生成有向路，那么稱它是有向可跡圖。由定理5，可以得出下面的推論。

推論6 設D是n個頂點的有向可跡圖，H是超歐拉有向圖，α=B1B2…Br∈Sn是一個置換。如果α連通，并且r≤3，那么D對H的α-廣義棱柱αH(D)是超歐拉有向圖。

證明 D是有向可跡圖，取它的一條生成有向路P。由于α∈Sn且α連通，所以由定理5可知，αH(P)是超歐拉有向圖。因為αH(P)是αH(D)的生成子有向圖，所以αH(D)也是超歐拉有向圖。證畢。

3 無向廣義棱柱的超歐拉性質

針對兩個無向圖G和H，可將有向廣義棱柱αH(D)的定義稍做修改，把H的每個頂點替換為G的一個復制，而把H的每一條邊替換為一組置換邊，即得無向廣義棱柱αH(G)，那么α(G)?αK2(G)，其中K2為兩個頂點的完全圖。這說明了由兩個圖G和H構造的廣義棱柱αH(G)，是文獻［3］中定義的一個圖G的α-廣義棱柱α(G)的推廣。

由定理4和推論6，很容易得到如下無向圖的廣義棱柱的超歐拉性質。

推論7 設G和H是超歐拉圖，|V(D)|=n，那么對于任意的α∈Sn，G對H的α-廣義棱柱αH(G)是超歐拉圖。

推論8 設G是n個頂點的可跡圖，H是超歐拉圖，α=B1B2…Br∈Sn是一個置換。如果α連通，并且r≤3，那么G對H的α-廣義棱柱αH(G)是超歐拉圖。