不含弦 6-圈的平面圖的線性 2-蔭度

常晶晶，徐常青

（ 河北工業(yè)大學(xué) 理學(xué)院，天津 300401）

不含弦 6-圈的平面圖的線性 2-蔭度

常晶晶，徐常青

（ 河北工業(yè)大學(xué) 理學(xué)院，天津 300401）

線性 2-森林是每個(gè)連通分支是長度至多為 2 的路的圖，圖 G 的線性 2-蔭度是將 G 邊分解為 k 個(gè)線性 2-森林 的最小 k 值 ，記為 la2G ．證 明了若 G 為不含弦 6-圈的平面圖 ，則 la2GG/2+6 ．

平面圖；蔭度；線性 2-蔭度；邊分解

0 引言

圖的線性 k- 蔭度是由 Habib 和 Peroche[1]提出的．目前已經(jīng)確定了某些特殊圖：圈、樹、完全圖、完全二部圖[2-4]的線性 2-蔭度．文獻(xiàn) [5] 得到了平面圖的線性 2-蔭度的一般上界，并給出了不同圍長的平面圖的線性 2-蔭度的上界．文獻(xiàn) [6] 改進(jìn)了平面圖線性 2-蔭度的一般上界，得到．文獻(xiàn) [7] 證明了每個(gè)不含弦 5-圈的平面圖的線性 2-蔭度滿足．本文證明了不含弦 6-圈的平面圖的線性 2-蔭度滿足

下面給出一些基本記法．設(shè)圖G為平面圖，用F G 表示圖G的面集合．任一表示面 f的度，即面 f邊界的長度．度 d f=i的面稱為 i面表示與頂點(diǎn) v 關(guān)聯(lián)的 i面數(shù)．任一表示頂點(diǎn) v 的度，在不引起混淆時(shí)簡記為 d v ．k- 點(diǎn)表示度為 k 的點(diǎn)，k+- 點(diǎn)表示度至少為 k 的點(diǎn)．稱一個(gè)偶圈為 2-交替圈，若滿足

定義1 任給平面圖G，若G的任意一個(gè)非平凡分支H都有下列情況之一成立：

引理 1[8]設(shè)圖 G 為平面圖，若 G 為 k,1-遺傳圖 （9k14），則

引理 2[9]設(shè)圖 G 為 G3 且不含弦 6-圈的平面圖，那么 G 中存在一條邊 xy ，使得 d x+d y9．

1 主要結(jié)果

因?yàn)?G 不含弦 6-圈，故不存在 4 個(gè)依次相鄰的 3 面，從而有斷言 1：

要證斷言 2成立，只需證與 v 關(guān)聯(lián)的任意6個(gè)依次相鄰的面中必有一個(gè) 5+面，用反證法證明此結(jié)論成立．設(shè)與 v 關(guān)聯(lián)的 6 個(gè)依次相鄰的面分別為 f1, ,f6，均為 3-面或 4-面．顯然不存在 3 個(gè)依次相鄰的 4面．由斷言 1 可知，每 6 個(gè)依次相鄰的面中至多有 3 個(gè) 3-面依次相鄰．

1） 存在 3 個(gè) 3-面依次相鄰．設(shè) fi,fi+1,fi+2為 3 個(gè)相鄰 3-面．

① i=1 （或者i+2=6)．不妨設(shè) i=1 ，即 f1,f2,f3為 3 個(gè)相鄰 3-面，f4為 4-面，此時(shí)當(dāng) f5為 3-面時(shí)，出現(xiàn)弦 6-圈．當(dāng) f5為 4-面時(shí)，出現(xiàn)弦 6-圈或者 2-交替圈，矛盾．

下面設(shè)沒有 3 個(gè)依次相鄰的 3-面．

2） 兩個(gè) 3-面相鄰．設(shè) fi,fi+1為 2 個(gè)相鄰 3-面．

① i=1 （或者i+1=6)．不妨設(shè) f1,f2為兩個(gè)相鄰 3-面，f3為 4-面，若 f4為 4-面，出現(xiàn)弦 6-圈或者 2-交替圈，故 f4為 3-面．若 f5為 3-面，出現(xiàn)弦 6-圈，故 f5為 4-面．當(dāng) f6為 3-面時(shí)，出現(xiàn)弦 6-圈．當(dāng) f6為4-面時(shí)，出現(xiàn)弦 6-圈或者 2-交替圈，矛盾．

3）任兩個(gè) 3-面不相鄰．

① f1為 3-面，f2為 4-面．當(dāng) f3為 4-面時(shí)，f4為 3-面，則出現(xiàn)弦 6-圈或 2-交替圈，矛盾．當(dāng) f3為 3-面時(shí)，f4為 4-面，而 f5為 3-面或 4-面，出現(xiàn)弦 6-圈或 2-交替圈，矛盾．② f1為 4-面．

若 f2為 4-面，則 f3為 3-面．從而 f4為 4-面．若 f5為 3-面，則出現(xiàn)弦 6-圈，故 f5為 4-面．若f6為 3-面，則出現(xiàn)弦 6-圈；若 f6為 4-面，則出現(xiàn)弦 6-圈或 2-交替圈，矛盾．

若 f2為 3-面，則 f3為 4-面．若 f4為 4-面，則 f5為 3-面，出現(xiàn)弦 6-圈或 2-交替圈，矛盾．若f4為 3-面，則 f5為 4-面，出現(xiàn)弦 6-圈，矛盾．

綜上可得斷言2成立．

下面運(yùn)用權(quán)轉(zhuǎn)移方法證明結(jié)論．

給定如下權(quán)轉(zhuǎn)移規(guī)則：

R1 每個(gè) 2-點(diǎn)從它的 2-主點(diǎn)得權(quán) 2．

R2 每個(gè) 3-面從與之相鄰的每個(gè) 5 點(diǎn)或 6 點(diǎn)得權(quán) 1 ；從每個(gè)與之相鄰的點(diǎn)得權(quán)

R3 每個(gè) 4-面從與之相鄰的每個(gè) 6+點(diǎn)得權(quán) 1 ．

R4 每個(gè) 5-面從與之相鄰的每個(gè) 6+點(diǎn)得權(quán)．

1） f v=5 ，由 G 不含弦 6-圈且無 2-交替圈，知，故由R2 得

3

34

3

4） f3v2 ，由及R2～ R4得

1） f3v=6 ，由斷言 2 知，因 G 不含弦 6-圈且無 2-交替圈，故有，由R1～R3 得

2） f3v=5 ，由斷言 2 有，若 f4v=2 ，則 f5v=0 ，由 R1～R4 得；若由 R1～R4得

34）， 斷言 2 有，由及 R1～R4得5），由及R1～R4得

1） f3v=7 ，因 G 不含弦 6-圈且無 2-交替圈，故有，由R1 ，R2 得

2） f3v=6 ， 由 斷 言 2 有， 且 由及 R 1～R 4 得

3） f3v=5 ， 由 斷 言 2 有， 且 由及 R 1～R 4 得

3

故結(jié)論成立．

由定理1知不含弦 6-圈的平面圖為 10,1-遺傳圖，故由引理 1 即得如下結(jié)論：

定理 2 若 G 為不含弦 6-圈的平面圖，則 la2GG/2+6 ．

[1]Habib M，Peroche B．Someproblemsabout lineararboricity[J]．DiscreteMath，1982，41（2）：219-220．

[2]Fu Hunglin，Huang Guoqing．The linear 2-arboricity of completebipartitegraphs[J]．ArsCombin，1994，38（3）：309-318．

[3]Chen Bailiang，F(xiàn)u Henglin，Huang Guoqing．Decomposing graphs into forestsof pathswith size less than three[J]．Australas JCombin，1991，3（1）：155-73．

[4]Yen Chihhung，F(xiàn)u Hunglin．Linear 2-arboricity of the completegraph[J]．Taiwanese JMath，2010，14（1）：273-286．

[5]Lih Kowei，Tong Lida，WangWeifan．The linear2-arboricity of planargraphs[J]．GraphsCombin，2003，19：241-248．

[6] 徐常青，安麗莎，杜亞濤．平面圖線性 2-蔭度的一個(gè)上界 [J]．山東大學(xué)學(xué)報(bào)：理學(xué)版，2014，49（4）：38-40．

[7] 田夏云．平面圖的線性蔭度和線性 2-蔭度 [D]．濟(jì)南：山東大學(xué)，2011：24．

[8]Xu Changqing，Chang Jingjing．The Linear2-Arboricity of Some Planar Graphs[J]．ArsCombin，2014，114：223-227．

[9] 錢景．圖的線性蔭度及線性 2-蔭度 [D]．金華：浙江師范大學(xué)，2006：18．

[責(zé)任編輯 楊 屹]

The linear2-arboricity of planargraphsw ithoutchordal-6-cycles

CHANG Jing-jing，XU Chang-qing
(Schoolof Science,HebeiUniversity of Technology,Tianjin 300401,China)

A linear2-forestisa forestwhose componentsare pathsof length atmost2．The linear2-arboricity ofagraph G ，is the leastinteger k,so that G can be decomposed into k linear2-forests,which isdenoted by la2G ．Weget that if G isa planargraphw ithoutchordal-6-cycles,then la2GG/2+6.

planargraph;arboricity;linear2-arboricity;edge decomposition

1007-2373(2014)05-0076-04

O157.5

A

10.14081/j.cnki.hgdxb.2014.05.014

2013-09-29

國家自然科學(xué)基金青年基金（11301134）；河北省自然科學(xué)基金（A2011202071）

常晶晶（1987），女（漢族），碩士生．通訊作者：徐常青（1970），女（漢族），教授．