與直徑和圍長有關(guān)的圖的最大虧格

劉端鳳,黃元秋,陽寧光

(1.廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院,廣東廣州 510006;2.湖南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,湖南長沙 410081;3.廣東商學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院,廣東廣州 510320)

與直徑和圍長有關(guān)的圖的最大虧格

劉端鳳1,黃元秋2,陽寧光3

(1.廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院,廣東廣州 510006;2.湖南師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,湖南長沙 410081;3.廣東商學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院,廣東廣州 510320)

直徑；Betti虧數(shù)；上可嵌入的；最大虧格

1 引言

定理A設(shè)G為圖,

設(shè)A?E(G)為圖G的一個邊子集,記號c(GX)表示GX的所有連通分支個數(shù);而記號b(GX)表示具有圈秩數(shù)為奇數(shù)的GX的所有連通分支個數(shù).對于圖G的任意點集X,X關(guān)于G的點導(dǎo)出子圖是以X為點集且以兩個端點均在X中的邊為邊集的G的子圖.文[4]給出了圖G的ξ(G)另外一個組合表達式:

最大虧格和虧格是圖的兩個重要拓撲參數(shù).研究圖的最大虧格的下界與圖的其它參數(shù)的關(guān)系一直是拓撲圖論中引人關(guān)注的問題.結(jié)合一個或多個參數(shù):比如說點的最小度[5]和直徑,許多文獻都給出了一系列圖的最大虧格的下界.特別地,關(guān)于圖的直徑與最大虧格下界的關(guān)系,近年來引起了圖論學(xué)者的重視.首先,文[6-8]分別考慮了直徑為2,3,4的情形,得到了一些很有意義的結(jié)果.文[9]在此基礎(chǔ)上,得到了如下結(jié)果:

結(jié)果1設(shè)G是直徑為d的簡單圖,若G的圍長也為d,則ξ(G)≤1,即圖G是上可嵌入的,其中d為不小于4的偶數(shù).

下面我們將用例子來說明,這個結(jié)果是錯誤的.

圖1 G1以及它的一個平面嵌入

在G1中,取A={e1,e2,e3},這里A?E(G1),由定理B,容易得到ξ(G1)≥{c(GA)+ b(GA)?|A|?1}=3+3?3?1=2,取T為G1的一棵樹,其中E(T)={E(G1)(f1,f2,f3,f4)}, V(T)=V(G1),此時ξ(G1,T)=2,由Betti虧數(shù)的定義知,ξ(G1)≤2,故ξ(G1)=2.從而說明結(jié)果1是錯誤的.文[9]的第二個結(jié)果:

在說明它的證明過程之前,我們要先給出一個引理.關(guān)于一個非上可嵌入圖,最近文[10]得到了如下結(jié)果:

引理1設(shè)G為圖,若ξ(G)≥2,即G不是上可嵌入的,則存在G的邊子集A,滿足下列性質(zhì):

1)c(GA)≥2,且對GA的任意連通分支F,有β(F)≡1(mod 2);

2)對GA的任意連通分支F,F是G的點導(dǎo)出子圖;

3)對GA的任意k(≥2)個不同連通分支F1,F2,…,Fk,則有|EG(F1,F2,…,Fk)|≤2k

?3;特別地,當(dāng)k=2時,|EG(F1,F2)|≤1; 4)ξ(G)=2c(GA)?|A|?1.下面是文[9]中結(jié)果2的證明.

結(jié)果2的證明若G是上可嵌入的,即ξ(G)≤1,則結(jié)論顯然成立.由文[7]知,d=3時,結(jié)論也成立.因此以下總假定G的直徑d≥4,并且不是上可嵌入的,即ξ(G)≥2.由引理1 知,存在G的邊子集A使得GA滿足引理1的所有性質(zhì)1)-4).

下面分三種情形來討論:

情形3若GA的連通分支數(shù)不少于4,設(shè)F1,F2,F3,F4為GA的任意4個連通分支,則它們中任何兩個連通分支均有一條邊相連(若不然,就會出現(xiàn)距離大于d的兩個頂點).此時有|E(F1,F2,F3,F4)|=6,這與引理1性質(zhì)3)|E(F1,F2,F3,F4)|≤2×4?3=5,矛盾.由情形3的證明過程可知,GA的連通分支個數(shù)不可能大于或等于4.但是我們可以找到具體的圖來說明這時候GA的連通分支個數(shù)是可以大于或等于4的.

圖2 G2以及它的一個平面嵌入

很明顯,在G2中,G2A的連通分支個數(shù)為4.但是,此時我們?nèi)={e1,e2,e3,e4,e5},這里A?E(G2),由定理B,容易得到ξ(G2)≥{c(GA)+b(GA)?|A|?1}=4+4?5?1=2,取T 為G2的一棵樹,其中E(T)={E(G2)(e1,f1,f4,e2,f2,f3)},V(T)=V(G2),此時ξ(G2,T)= 2,由Betti虧數(shù)的定義知,ξ(G2)≤2.故ξ(G2)=2.也就說明了文[9]的證明過程是不嚴謹?shù)?

下面我們給出正確的結(jié)果并證明之.

2 定理的證明

若G是上可嵌入的,即ξ(G)≤1,則結(jié)論顯然成立.由文[6]知,d=3時,結(jié)論也成立.因此以下總假定G的直徑d≥4,并且不是上可嵌入的,即ξ(G)≥2.由引理1知,存在G的邊子集A使得GA滿足引理1的所有性質(zhì).下面我們約定如下記號:

對任意集合X,|X|表示X的基數(shù);

用ψ表示GA的所有連通分支組成的集合,此時為了方便我們把ψ中的元素與GA的連通分支無區(qū)別地看待;

由定理的證明過程易知,若將定理的條件“G的圍長為d”改為“G的圍長不小于d”,而其他條件不變,其結(jié)論仍然成立.

注文中圖1和圖2同時說明了定理中關(guān)于γM(G)的下界也是最好的.

[1]Bondy J A,M urty U SR.G raph Theory with App lication[M].London:M acm illan,1976.

[2]Nordhaus E,Stewart B，W hite A.On the maximum genus of a graph[J].J.Combinatorial Theory B, 1971,11:258-267.

[3]劉彥佩.圖的可嵌入性理論[M].北京:科學(xué)出版社,1994.

[4]Nebesky L.A new characterization of them aximum of a graph[J].J.Czechoslovak M ath.,1981,31(106):604-613.

[5]蘇本堂,苗蓮英.最小度和[a,b]-因子[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2003,19(4):63-66

[6]Skoviera M.Them aximum genus of graph s of diam eter two[J].Discrete Mathem atics,1991,87:175-180.

[7]Hunglin Fu,minchu Tsai.Themaximum genus of diameter three graphs[J].Australasian JCombinato-rics, 1996,14:187-197.

[8]黃元秋,劉彥佩.關(guān)于直徑為4的圖的最大虧格[J].數(shù)學(xué)物理學(xué)報:A,2001,21(3):349-354.

[9]盛秀艷.與直徑和圍長有關(guān)的最大虧格的下界[J].數(shù)學(xué)學(xué)報,2004,47(6):1201-1204.

[10]黃元秋,劉彥佩.圖的上可嵌入性[J].中國科學(xué):A輯,1998,28(3):223-228.

(1.Departm ent of App lied Mathem atics,Guangdong University of Technology,Guangzhou 510006,China; 2.Department of Mathematics and Com puter Science,Hunan Normal University,Changsha 410081,China; 3.Departm ent of Mathem atics and Com puter Science,Guangdong University of Business Studies, Guangzhou 510320,China)

The maximum genus on graphs in terms of diameter and girth

LIU Duan-feng1,HUANG Yuan-qiu2,YANG Ning-guang3

diam eter,Betti deficiency number,upper embeddab le,m aximum genus 2000M SC:05C

O157.5

A

1008-5513(2009)02-0284-05

2007-12-10.

國家自然科學(xué)基金(10771062),教育部新世紀優(yōu)秀人才支持項目(NCET-07-0276),廣東工業(yè)大學(xué)校青年基金(062060).

劉端鳳(1976-),在讀博士,講師,研究方向：圖論及其應(yīng)用和計算機輔助幾何設(shè)計.