上可嵌入图与次上可嵌入图的线性荫度

吕长青

（枣庄学院数学与统计学院，山东枣庄277160）

上可嵌入图与次上可嵌入图的线性荫度

吕长青

（枣庄学院数学与统计学院，山东枣庄277160）

通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度，证明了最大度Δ不小于且欧拉示性数ε≤0的上可嵌入图其线性荫度为■■.对于次上可嵌入图，如果最大度Δ≥3■4-3ε且ε≤0，则其线性荫度为■■.改进了文献［1］中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度.

线性荫度；曲面；（次）上可嵌入图；欧拉示性数

0引言

本文研究的图都是简单连通无向图，所有的专业术语均可参考文献［2］.

设图G=（V,E），令N（v）=｛u|uv∈E（G）｝，Nk（v）=｛u|u∈N（v）,d（u）=k｝，这里d（v）=|N（v）|是点v度.记Δ（G）和δ（G）分别表示图的最大度与最小度，如果一个点的度为k称该点为k-点.

曲面是一个紧的连通的2-维闭流形.曲面可分为可定向曲面与不可定向曲面.一个可定向曲面Sh（h≥0）是由一个球面添上h个环柄得到.不可定向曲面Nk（k≥1）是由一个球面挖掉k个圆盘而分别补上Möbius带得到.如不加特别说明本文讨论的曲面都是可定向曲面.

如果一个图画在曲面Σ上使得它的边仅仅在端点处相交，则称这个图嵌入到曲面Σ上.图G嵌入曲面Σ上称为2-胞腔嵌入，如果Σ-G中每个分支同胚于一个开圆盘.此时，每个分支称为G在曲面Σ上嵌入的一个面.一个嵌入图的面度是指与这个面相关联的边的个数，如果一个面f的度为k，则称f为k-面；如果一个面f的度大于等于k，则称f为k+-面.

一个曲面Σ的Euler示性数ε（Σ）（文献［3］）定义如下：当Σ=Sh时，ε（Σ）=2-2h；当Σ=Nk时，ε（S）=2-k.

Euler公式［3］设G是一个2-胞腔嵌入在曲面Σ上的图，如果G有V（G）个顶点，E（G）条边，在曲面S上有F（G）个面，则|V（G）|-|E（G）|+|F（G）|=ε.

图的最大亏格是指存在一个最大的整数k使得G能嵌入到Sk上，记作γM（G）.由于连通图的二胞腔嵌入至少有一个面，由欧拉公式可得：γM（G）≤［］，这里β（G）（=|E（G）|-|V（G）|+1）称为图G的Betti数（或圈秩）.一个连通图G是上可嵌入的如果γM（G）=［］；称一个图G是次上可嵌入的如果γM（G）=］-1.由于不连通图不能二胞腔嵌入到任何曲面上，所以本文讨论的都是连通图.

称一个映射φ：→｛1,2,···,t｝为图G的一个t-线性染色，如果对于任意的1≤α≤t时（V（G）,φ-1（α））的边导出子图是一个线森；一个图的线性荫度是其所有t-线性染色中最小的数t，记作la（G）.Akiyama、Exoo和Harary在文献［4］给出了对任意的正则图G，其线性荫度满足la（G）=■（Δ（G）+1）/2■.由于对任意的图G，la（G）≥■Δ（G）/2■，由此可得到著名的线性荫度猜想.

猜想1［4］对任意的图G，■■≤la（G）≤■■.

对于一些图类猜想1被证明是正确的，如完全二部图，Halin图，系列平行图，完全正则多部图等（文献［4-7］）；对于平面图，猜想1是成立的（文献［9］）.Wu在文献［10］中证明了平面图G，如果Δ≥13，则la（G）=■Δ/2■，并将这个结果推广到欧拉示性数ε≥0的曲面嵌入图；文献［8］又给出了当欧拉示性数ε≤0，且最大度Δ（G）不小于■46-54ε+19时，la（G）=■Δ/2■.论文［1］证明了当欧拉示性数ε≤0，当Δ（G）≥■45-45ε+10时，la（G）=■Δ/2■，改进了文献［8］中最大度的下界.

本文讨论了上可嵌入图以及次上可嵌入图的线性荫度，证明了下面定理并进一步改进了文献［8］最大度的下界.图1所示是欧拉示性数-6≤ε≤-1曲面嵌入图G结果.

定理1设图G是上可嵌入图且ε≤0，且最大度Δ（G）≥3■4-3ε时，la（G）=■■.

定理2设图G是次上可嵌入图且ε≤0，且最大度Δ（G）≥6■1-ε时，la（G）=■■.

一个图G称为稀疏图如果|E（G）|=O（|V（G）|）.对于给定的欧拉示性数ε且满足定理1或定理2最大度下界时，该图为稀疏图，因此本文讨论的图类为稀疏图.

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.

假设G是使定理1或定理2中的结论不成立的最小反例，则有如下引理成立（文献［8］）.

引理1.3［8］对于任意的边uv∈E（G），则dG（u）+dG（v）≥Δ（G）+2.

由引理1.1，可知δ（G）≥2且任意两个2-点不相邻.

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

设G2是由2-点相关联边的导出子图，M是G中饱和G2的2-点的匹配.如果uv∈M且d（u）=2，那么称v为u的一个2-master.显然每个2-点都有一个2-master，它必然是最大度点，每一个最大度点至多是一个2-点的2-master.

引理1.6［8］如果Xt/=∅，那么存在Kt的二部子图Mt使得对于每一个x∈Xt时dMt（x）= 1，且对任意的y∈Yt，0≤dMt（y）≤2t-1.

在图G中，如果xy∈Mt，则称y是x的t-master.由引理1.4可得对于任意的i和j（2≤i≤j≤3），则每一个i-点都有j-master.

2定理及其证明

定理1设图G是上可嵌入图且ε≤0，且最大度Δ（G）≥3■时，la（G）=■■.

证明假设图G是使定理不成立的最小反例.由欧拉公式|V（G）|-|E（G）|+|F（G）|=ε，可得由引理1.1可知，

对于任意的x∈V（G），定义ch（x）=d（x）-3，根据下面给出的规则，对于每一个x∈V（G），重新分配新的值记作ch′（x）.由于重新分配值不影响整个的和，所以如果对每一个x∈V（G）能够得到ch′（x）＞-3ε.这就得到了矛盾.下面给出度重新分配值的规则.

R1每一个2-点从它的2-masters接受值1.

R2如果3≤d（v）≤Δ（G）-1，那么v点即不接受值也不分值.

断言对任意的v∈V，则ch′（v）≥0；特别的如果

证明如果d（v）=2，那么ch′（v）≥0，这是因为v从它的2-masters接受值为1；如果d（v）=3，那么ch′（v）=0；如果4≤d（v）≤Δ（G）-1，那么v既不接受也不分配值，对于每一个u∈N（v）由引理1.3可知dG（u）≥3，所以ch′（v）=ch（v）=d（v）-3≥0；如果

如果d（v）=Δ（G），那么对于u∈N（v）有dG（u）≥2，这可以推出v是1个点的2-master，所以ch′（v）≥（Δ（G）-3）-1）.

定理2设图G是次上可嵌入图且ε≤0，且最大度Δ（G）≥6■1-ε时，la（G）=■.

证明假设图G是使定理不成立的最小反例.由欧拉公式|V（G）|-|E（G）|+|F（G）|=ε，可得

对于任意的x∈V（G），定义ch（x）=d（x）-3，根据下面给出的规则，对于每一个x∈V（G），重新分配新的值记作ch′（x）.由于重新分配值不影响整个的和，所以

如果对每一个x∈V（G）能够得到ch′（x）＞-3ε.这就得到了矛盾.下面给出度重新分配值的规则.

R1每一个2-点从它的2-masters接受值1.

R2如果3≤d（v）≤Δ（G）-1，那么v点即不接受值也不分值.

类似于定理1的证明，可得

对任意的v∈V，则ch′（v）≥0；特别的如果d（v）≥■■，则ch′（v）≥■■-2.

令U=｛u|dG（u）≤■■｝，W=N（U）.由引理1.3可知U是G的独立集.设F是G导出二部子图，U和W是F的分部.如果|V（G）U|≤■■+1，那么对于每个点w∈W，F是图G的（■■）-alternating，与引理1.6矛盾.所以-3ε,矛盾.这样就完成了定理2的证明.

称可定向曲面S2为双环面；称图G三角剖分曲面Σ如果图G嵌入到曲面Σ上且每个面的面度为3.

定理3设图G是双环面的三角剖分图，且能上可嵌入到欧拉示性数为ε≤-2曲面上，当最大度

证明假设图G是使定理不成立的最小反例.由于图G嵌入到S2，由欧拉公式|V（G）|-|E（G）|+|F（G）|=-2，可得

由于G可三角剖分S2，所以3|V（G）|=3|V（G）|+12，所以由于G能上可嵌入到欧拉示性数为ε≤-2曲面上，可得

对于任意的x∈V（G）），定义ch（x）=d（x）-3，根据下面给出的规则，对于每一个x∈V（G），重新分配新的值记作ch′（x）.由于重新分配值不影响整个的和，所以

如果对每一个x∈V（G）能够得到ch′（x）＞6-ε.这就得到了矛盾.下面给出度重新分配值的规则.

R1每一个2-点从它的2-masters接受值1.

R2如果3≤d（v）≤Δ（G）-1，那么v点即不接受值也不分值.

类似于定理1中的证明可得

对任意的v∈V，则ch′（v）≥0；特别的如果d（v）≥■■，则ch′（v）≥■■-2.

令U=｛u|dG（u）≤■■｝，W=N（U）.由引理1.3可知U是G的独立集.设F是G导出二部子图，U和W是F的分部.如果|V（G）U|≤■■+1，那么对于每个点w∈W，F是图G的（■）-alternating，与引理1.6矛盾.所以|V（G）U|≥■■+2.这样矛盾.这样就完成了定理3的证明.

［1］吕长青.较大亏格嵌入图的线性荫度［J］.华东师范大学学报：自然科学版，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.

（责任编辑李艺）

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

国家自然科学基金（11101357，61075033）

吕长青，男，副教授，研究方向为图论、运筹学.E-mail：cqiqc1999@126.com.