廣義棱柱中的超歐拉有向圖

牛兆宏，馮雅瓊，王劉巖

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

0 引言

本文只考慮有限無(wú)環(huán)的圖和有向圖，沒(méi)有特殊說(shuō)明的話，圖指的是無(wú)向圖。文中未定義的符號(hào)和術(shù)語(yǔ)，無(wú)向圖參見(jiàn)文獻(xiàn)［1］，有向圖參見(jiàn)文獻(xiàn)［2］。

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

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

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

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

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

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

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

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

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

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

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

綜上所述，引理得證。

2 有向廣義棱柱的超歐拉性質(zhì)

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

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

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

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

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

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

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

這就證明了定理5。

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

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

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

3 無(wú)向廣義棱柱的超歐拉性質(zhì)

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

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

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

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