呂長(zhǎng)青

（棗莊學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，山東棗莊277160）

上可嵌入圖與次上可嵌入圖的線性蔭度

呂長(zhǎng)青

（棗莊學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，山東棗莊277160）

通過度再分配的方法研究上可嵌入圖與次上可嵌入圖的線性蔭度，證明了最大度Δ不小于且歐拉示性數(shù)ε≤0的上可嵌入圖其線性蔭度為■■.對(duì)于次上可嵌入圖，如果最大度Δ≥3■4-3ε且ε≤0，則其線性蔭度為■■.改進(jìn)了文獻(xiàn)［1］中最大度的的界.作為應(yīng)用證明了雙環(huán)面上的三角剖分圖的線性蔭度.

線性蔭度；曲面；（次）上可嵌入圖；歐拉示性數(shù)

0引言

本文研究的圖都是簡(jiǎn)單連通無向圖，所有的專業(yè)術(shù)語(yǔ)均可參考文獻(xiàn)［2］.

設(shè)圖G=（V,E），令N（v）=｛u|uv∈E（G）｝，Nk（v）=｛u|u∈N（v）,d（u）=k｝，這里d（v）=|N（v）|是點(diǎn)v度.記Δ（G）和δ（G）分別表示圖的最大度與最小度，如果一個(gè)點(diǎn)的度為k稱該點(diǎn)為k-點(diǎn).

曲面是一個(gè)緊的連通的2-維閉流形.曲面可分為可定向曲面與不可定向曲面.一個(gè)可定向曲面Sh（h≥0）是由一個(gè)球面添上h個(gè)環(huán)柄得到.不可定向曲面Nk（k≥1）是由一個(gè)球面挖掉k個(gè)圓盤而分別補(bǔ)上M?bius帶得到.如不加特別說明本文討論的曲面都是可定向曲面.

如果一個(gè)圖畫在曲面Σ上使得它的邊僅僅在端點(diǎn)處相交，則稱這個(gè)圖嵌入到曲面Σ上.圖G嵌入曲面Σ上稱為2-胞腔嵌入，如果Σ-G中每個(gè)分支同胚于一個(gè)開圓盤.此時(shí)，每個(gè)分支稱為G在曲面Σ上嵌入的一個(gè)面.一個(gè)嵌入圖的面度是指與這個(gè)面相關(guān)聯(lián)的邊的個(gè)數(shù)，如果一個(gè)面f的度為k，則稱f為k-面；如果一個(gè)面f的度大于等于k，則稱f為k+-面.

一個(gè)曲面Σ的Euler示性數(shù)ε（Σ）（文獻(xiàn)［3］）定義如下：當(dāng)Σ=Sh時(shí)，ε（Σ）=2-2h；當(dāng)Σ=Nk時(shí)，ε（S）=2-k.

Euler公式［3］設(shè)G是一個(gè)2-胞腔嵌入在曲面Σ上的圖，如果G有V（G）個(gè)頂點(diǎn)，E（G）條邊，在曲面S上有F（G）個(gè)面，則|V（G）|-|E（G）|+|F（G）|=ε.

圖的最大虧格是指存在一個(gè)最大的整數(shù)k使得G能嵌入到Sk上，記作γM（G）.由于連通圖的二胞腔嵌入至少有一個(gè)面，由歐拉公式可得：γM（G）≤［］，這里β（G）（=|E（G）|-|V（G）|+1）稱為圖G的Betti數(shù)（或圈秩）.一個(gè)連通圖G是上可嵌入的如果γM（G）=［］；稱一個(gè)圖G是次上可嵌入的如果γM（G）=］-1.由于不連通圖不能二胞腔嵌入到任何曲面上，所以本文討論的都是連通圖.

稱一個(gè)映射φ：→｛1,2,···,t｝為圖G的一個(gè)t-線性染色，如果對(duì)于任意的1≤α≤t時(shí)（V（G）,φ-1（α））的邊導(dǎo)出子圖是一個(gè)線森；一個(gè)圖的線性蔭度是其所有t-線性染色中最小的數(shù)t，記作la（G）.Akiyama、Exoo和Harary在文獻(xiàn)［4］給出了對(duì)任意的正則圖G，其線性蔭度滿足la（G）=■（Δ（G）+1）/2■.由于對(duì)任意的圖G，la（G）≥■Δ（G）/2■，由此可得到著名的線性蔭度猜想.

猜想1［4］對(duì)任意的圖G，■■≤la（G）≤■■.

對(duì)于一些圖類猜想1被證明是正確的，如完全二部圖，Halin圖，系列平行圖，完全正則多部圖等（文獻(xiàn)［4-7］）；對(duì)于平面圖，猜想1是成立的（文獻(xiàn)［9］）.Wu在文獻(xiàn)［10］中證明了平面圖G，如果Δ≥13，則la（G）=■Δ/2■，并將這個(gè)結(jié)果推廣到歐拉示性數(shù)ε≥0的曲面嵌入圖；文獻(xiàn)［8］又給出了當(dāng)歐拉示性數(shù)ε≤0，且最大度Δ（G）不小于■46-54ε+19時(shí)，la（G）=■Δ/2■.論文［1］證明了當(dāng)歐拉示性數(shù)ε≤0，當(dāng)Δ（G）≥■45-45ε+10時(shí)，la（G）=■Δ/2■，改進(jìn)了文獻(xiàn)［8］中最大度的下界.

本文討論了上可嵌入圖以及次上可嵌入圖的線性蔭度，證明了下面定理并進(jìn)一步改進(jìn)了文獻(xiàn)［8］最大度的下界.圖1所示是歐拉示性數(shù)-6≤ε≤-1曲面嵌入圖G結(jié)果.

定理1設(shè)圖G是上可嵌入圖且ε≤0，且最大度Δ（G）≥3■4-3ε時(shí)，la（G）=■■.

定理2設(shè)圖G是次上可嵌入圖且ε≤0，且最大度Δ（G）≥6■1-ε時(shí)，la（G）=■■.

一個(gè)圖G稱為稀疏圖如果|E（G）|=O（|V（G）|）.對(duì)于給定的歐拉示性數(shù)ε且滿足定理1或定理2最大度下界時(shí)，該圖為稀疏圖，因此本文討論的圖類為稀疏圖.

1引理

證明：由于G是上可嵌入圖，所以G為單面或雙面嵌入圖.由歐拉公式可知|E（G）|= |V（G）|+|F（G）|-ε，由于Δ（G）≥3＞7，所以|E（G）|=|V（G）|+|F（G）|-ε＞8+1+1，即|E（G）|＞10，又由于

證明由于G是次上可嵌入圖，所以G為3或4面嵌入圖.由歐拉公式可知|E（G）|= |V（G）|+|F（G）|-ε，以及Δ（G）≥6■＞8，所以|E（G）|=|V（G）|+|F（G）|-ε＞9+3+1，即|E（G）|＞13，又由于■f∈F（d（f）-6）=2E（G）-6F（G）≥0.

假設(shè)G是使定理1或定理2中的結(jié)論不成立的最小反例，則有如下引理成立（文獻(xiàn)［8］）.

引理1.3［8］對(duì)于任意的邊uv∈E（G），則dG（u）+dG（v）≥Δ（G）+2.

由引理1.1，可知δ（G）≥2且任意兩個(gè)2-點(diǎn)不相鄰.

引理1.4［8］G不含偶圈v0v1···v2n-1v0使得d（v1）=d（v3）=···=d（v2n-1）=

設(shè)G2是由2-點(diǎn)相關(guān)聯(lián)邊的導(dǎo)出子圖，M是G中飽和G2的2-點(diǎn)的匹配.如果uv∈M且d（u）=2，那么稱v為u的一個(gè)2-master.顯然每個(gè)2-點(diǎn)都有一個(gè)2-master，它必然是最大度點(diǎn)，每一個(gè)最大度點(diǎn)至多是一個(gè)2-點(diǎn)的2-master.

引理1.6［8］如果Xt/=?，那么存在Kt的二部子圖Mt使得對(duì)于每一個(gè)x∈Xt時(shí)dMt（x）= 1，且對(duì)任意的y∈Yt，0≤dMt（y）≤2t-1.

在圖G中，如果xy∈Mt，則稱y是x的t-master.由引理1.4可得對(duì)于任意的i和j（2≤i≤j≤3），則每一個(gè)i-點(diǎn)都有j-master.

2定理及其證明

定理1設(shè)圖G是上可嵌入圖且ε≤0，且最大度Δ（G）≥3■時(shí)，la（G）=■■.

證明假設(shè)圖G是使定理不成立的最小反例.由歐拉公式|V（G）|-|E（G）|+|F（G）|=ε，可得由引理1.1可知，

對(duì)于任意的x∈V（G），定義ch（x）=d（x）-3，根據(jù)下面給出的規(guī)則，對(duì)于每一個(gè)x∈V（G），重新分配新的值記作ch′（x）.由于重新分配值不影響整個(gè)的和，所以如果對(duì)每一個(gè)x∈V（G）能夠得到ch′（x）＞-3ε.這就得到了矛盾.下面給出度重新分配值的規(guī)則.

R1每一個(gè)2-點(diǎn)從它的2-masters接受值1.

R2如果3≤d（v）≤Δ（G）-1，那么v點(diǎn)即不接受值也不分值.

斷言對(duì)任意的v∈V，則ch′（v）≥0；特別的如果

證明如果d（v）=2，那么ch′（v）≥0，這是因?yàn)関從它的2-masters接受值為1；如果d（v）=3，那么ch′（v）=0；如果4≤d（v）≤Δ（G）-1，那么v既不接受也不分配值，對(duì)于每一個(gè)u∈N（v）由引理1.3可知dG（u）≥3，所以ch′（v）=ch（v）=d（v）-3≥0；如果

如果d（v）=Δ（G），那么對(duì)于u∈N（v）有dG（u）≥2，這可以推出v是1個(gè)點(diǎn)的2-master，所以ch′（v）≥（Δ（G）-3）-1）.

定理2設(shè)圖G是次上可嵌入圖且ε≤0，且最大度Δ（G）≥6■1-ε時(shí)，la（G）=■.

證明假設(shè)圖G是使定理不成立的最小反例.由歐拉公式|V（G）|-|E（G）|+|F（G）|=ε，可得

對(duì)于任意的x∈V（G），定義ch（x）=d（x）-3，根據(jù)下面給出的規(guī)則，對(duì)于每一個(gè)x∈V（G），重新分配新的值記作ch′（x）.由于重新分配值不影響整個(gè)的和，所以

如果對(duì)每一個(gè)x∈V（G）能夠得到ch′（x）＞-3ε.這就得到了矛盾.下面給出度重新分配值的規(guī)則.

R1每一個(gè)2-點(diǎn)從它的2-masters接受值1.

R2如果3≤d（v）≤Δ（G）-1，那么v點(diǎn)即不接受值也不分值.

類似于定理1的證明，可得

對(duì)任意的v∈V，則ch′（v）≥0；特別的如果d（v）≥■■，則ch′（v）≥■■-2.

令U=｛u|dG（u）≤■■｝，W=N（U）.由引理1.3可知U是G的獨(dú)立集.設(shè)F是G導(dǎo)出二部子圖，U和W是F的分部.如果|V（G）U|≤■■+1，那么對(duì)于每個(gè)點(diǎn)w∈W，F(xiàn)是圖G的（■■）-alternating，與引理1.6矛盾.所以-3ε,矛盾.這樣就完成了定理2的證明.

稱可定向曲面S2為雙環(huán)面；稱圖G三角剖分曲面Σ如果圖G嵌入到曲面Σ上且每個(gè)面的面度為3.

定理3設(shè)圖G是雙環(huán)面的三角剖分圖，且能上可嵌入到歐拉示性數(shù)為ε≤-2曲面上，當(dāng)最大度

證明假設(shè)圖G是使定理不成立的最小反例.由于圖G嵌入到S2，由歐拉公式|V（G）|-|E（G）|+|F（G）|=-2，可得

由于G可三角剖分S2，所以3|V（G）|=3|V（G）|+12，所以由于G能上可嵌入到歐拉示性數(shù)為ε≤-2曲面上，可得

對(duì)于任意的x∈V（G）），定義ch（x）=d（x）-3，根據(jù)下面給出的規(guī)則，對(duì)于每一個(gè)x∈V（G），重新分配新的值記作ch′（x）.由于重新分配值不影響整個(gè)的和，所以

如果對(duì)每一個(gè)x∈V（G）能夠得到ch′（x）＞6-ε.這就得到了矛盾.下面給出度重新分配值的規(guī)則.

R1每一個(gè)2-點(diǎn)從它的2-masters接受值1.

R2如果3≤d（v）≤Δ（G）-1，那么v點(diǎn)即不接受值也不分值.

類似于定理1中的證明可得

對(duì)任意的v∈V，則ch′（v）≥0；特別的如果d（v）≥■■，則ch′（v）≥■■-2.

令U=｛u|dG（u）≤■■｝，W=N（U）.由引理1.3可知U是G的獨(dú)立集.設(shè)F是G導(dǎo)出二部子圖，U和W是F的分部.如果|V（G）U|≤■■+1，那么對(duì)于每個(gè)點(diǎn)w∈W，F(xiàn)是圖G的（■）-alternating，與引理1.6矛盾.所以|V（G）U|≥■■+2.這樣矛盾.這樣就完成了定理3的證明.

［1］呂長(zhǎng)青.較大虧格嵌入圖的線性蔭度［J］.華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，1：7-10.

［2］BONDY J A，MURTY U S R.Graph Theory with Applications［M］.New York：Macmilan Ltd Press，1976.

［3］MOHAR B，THOMASSEN C.Graphs on Surfaces［M］.Baltimore：Johns Hopkins University Press，2001：85-85.

［4］AKIYAMA J，EXOO G，HARARY F.Covering and packing in graphs III：Cyclic and acyclic invariants［J］.Math Slovaca，1980（30）：405-417.

［5］A¨I-DJAFER H.Linear arboricity for graphs with multiple edges［J］.Journal of Graph Theory，1987（11）：135-140.

［6］WU J L.Some path decompositions of Halin graphs［J］.Journal of Shandong Mining Institute，1998（17）：92-96.

［7］WU J L.The linear arboricity of series-parallel graphs［J］.Graph and Combinatorics，2000（16）：367-372.

［8］WU J L.The Linear arboricity of graphs on surfaces of negative Euler characteristic［J］.SIAM J Discrete Math，2008（23）：54-58.

［9］WU J L，WU Y W.The linear arboricity of planar graphs of maximum degree seven is four［J］.Journal of Graph Theory，2008（58）：210-220.

［10］WU J L.On the linear arboricity of planar graphs［J］.Journal of Graph Theory，1999（31）：129-134.

［11］WU J L，LIU G Z，WU Y L.The linear arboricity of composition graphs［J］.Journal of System Science and Complexity，2002（15）：3 72-375.

［12］AHIYAMA J，EXOO G，HARARY F.Covering and packing in graphs IV：Linear arboricity［J］.Networks，1981（11）：69-72.

（責(zé)任編輯李藝）

The linear arboricity of upper-embedded graph and secondary upper-embedded graph

LYU Chang-qing
（School of Mathematics and Statistics，Zaozhuang University，Zaozhuang Shandong，277160，China）

The linear arboricity of a graph G is the minimum number of linear forests which partition the edges of G.In the present，it is proved that if a upper-embedded graph G has Δ≥then its linear arboricity is■■and if a secondary upper-embedded graph G has Δ≥then its linear arboricity is■■，where ε≤0.It improves the bound of the conclusion in［1］.As its application，the linear arboricity of a triangulation graph on double torus is concluded.

linear arboricity；surface；（secondary）upper-embedded graph；Euler characteristic

O157.5

A

10.3969/j.issn.1000-5641.2015.01.016

1000-5641（2015）01-0131-05

2014-04

國(guó)家自然科學(xué)基金（11101357，61075033）

呂長(zhǎng)青，男，副教授，研究方向?yàn)閳D論、運(yùn)籌學(xué).E-mail：cqiqc1999@126.com.