劉維嬋
LIU Weichan
西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,西安 710071
School of Mathematics and Statistics,Xidian University,Xi’an 710071,China
圖論是一門(mén)古老的數(shù)學(xué)分支,它起源于1736年歐拉對(duì)于哥尼斯堡七橋問(wèn)題的研究。近年來(lái),圖論學(xué)科的發(fā)展非常迅速且應(yīng)用廣泛,已滲透到諸如語(yǔ)言學(xué)、物理學(xué)、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其他分支中,特別在計(jì)算機(jī)科學(xué)中,圖論在如形式語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、分布式系統(tǒng)、操作系統(tǒng)等方面均扮演著重要的角色。
本文研究圖的拓?fù)浣Y(jié)構(gòu),只考慮簡(jiǎn)單圖。如果一個(gè)圖可以畫(huà)(嵌入)在平面上,使得不同的邊互不交叉,則稱這樣的圖是平面圖,否則稱為非平面圖。一個(gè)平面圖在平面上的嵌入稱為平圖。對(duì)于平圖G,用V(G)、E(G)、F(G)分別表示它的點(diǎn)集合、邊集合、面集合。著名的歐拉公式表明:
設(shè)G為一個(gè)圖在平面上的嵌入,如果圖G上存在交叉,則必然是G的某兩條邊交叉產(chǎn)生的,于是G中的每個(gè)交叉c都可以與G中的4個(gè)頂點(diǎn)(即兩條交叉邊上的4個(gè)頂點(diǎn))所構(gòu)成的點(diǎn)集建立對(duì)應(yīng)關(guān)系,稱這個(gè)對(duì)應(yīng)關(guān)系為θ。如果對(duì)于G中任何兩個(gè)不同的交叉(如果存在的話)c1與c2,有|θ(c1)?θ(c2)|≤1,則稱圖 G 是NIC-平面圖。NIC-平面圖的概念是由Zhang[1]于2014年提出的。容易看出,每個(gè)平面圖都是NIC-平面圖。
設(shè)?是一個(gè)圖類,如果對(duì)于?中的任何一個(gè)圖G,都存在一條邊uv以及一個(gè)與圖G的選擇無(wú)關(guān)的常數(shù)ω,使得d(u)+d(v)≤ω,則稱圖類?含有輕邊。Kotzig[2]證明了每個(gè)3-連通的平面圖都含有一條邊uv,其兩個(gè)頂點(diǎn)的度和至多為13。Fabrici與Madaras[3]證明了每個(gè)3-連通的1-平面圖都含有一條邊uv,其兩個(gè)頂點(diǎn)的度都不會(huì)超過(guò)20。具有最小度限制條件的1-平面圖的輕邊或其他輕子圖的存在性的研究可參見(jiàn)文獻(xiàn)[4-12]。
下文中,對(duì)于NIC-平面圖G,用δ(G)表示它的最小度,即度數(shù)(點(diǎn)所關(guān)聯(lián)的邊的條數(shù))最小的頂點(diǎn)的度數(shù);用g(G)表示它的圍長(zhǎng),即圖G所包含的所有圈中長(zhǎng)度(圈所關(guān)聯(lián)的邊的條數(shù))最短的圈的長(zhǎng)度;用GX表示圖G的關(guān)聯(lián)平面圖,即將圖G的所有交叉全部看成是一個(gè)新的度數(shù)為4的點(diǎn)所得到的平圖,這些新的點(diǎn)稱為圖GX的假點(diǎn),其余的點(diǎn)稱為圖GX的真點(diǎn);在圖GX中關(guān)聯(lián)假點(diǎn)的面稱為假面,其余的面稱為真面;k-點(diǎn)(面)或k+-點(diǎn)(面)指的是度數(shù)為k或至少為k的點(diǎn)(面)。其余未明確指出的定義或者記號(hào)可參閱文獻(xiàn)[7]。
設(shè)G是一個(gè)圍長(zhǎng)至少為5的NIC-平面圖?,F(xiàn)從圖G的每一對(duì)交叉邊中去除一條,得到圖H。容易看出,圖H是一個(gè)圍長(zhǎng)至少為5的平面圖。根據(jù)歐拉公式(1),可以得到[13]:
另一方面,Zhang[1]于2014年證明了圖G的交叉數(shù)至多為3(|V(G)|-2)/5,因此:
從而圖G的平均度為2|E(G)|/|V(G)|<5,由此可得δ(G)≤4,即每個(gè)圍長(zhǎng)至少為5的NIC-平面圖都含有一個(gè)度數(shù)不超過(guò)4的點(diǎn)。基于此,本文將研究圍長(zhǎng)至少為5且最小度為4的NIC-平面圖的輕邊存在性,并探討其在定向染色中的應(yīng)用。
定理1設(shè)G是NIC-平面圖,如果δ(G)=4且g(G)≥5,則G存在邊uv,其中d(u)=d(v)=4。
證明 假設(shè)該命題的結(jié)論不成立,即對(duì)于G的任何一條邊uv,當(dāng)d(u)=4時(shí),有d(v)≥5。
考慮圖G的關(guān)聯(lián)平面圖GX,由于它是平面圖,故根據(jù)歐拉公式(1),有:
對(duì)于圖GX的每個(gè)點(diǎn)v,定義權(quán)值c(v)=d(v)-6,對(duì)于每個(gè)面 f,定義權(quán)值c(f)=2d(f)-6。從而由式(2)可知:
接下來(lái),定義權(quán)轉(zhuǎn)移規(guī)則如下:
(R1)每個(gè)4-面向其關(guān)聯(lián)的假4-點(diǎn)轉(zhuǎn)移1/2。
(R2)設(shè) f=uvwx為4-面且 x為假4點(diǎn),如果v是真4-點(diǎn),則 f向v轉(zhuǎn)移5/6;如果u或w是真4-點(diǎn),則 f向u或w轉(zhuǎn)移1/2。
(R3)每個(gè)4+-面向其關(guān)聯(lián)的5-點(diǎn)轉(zhuǎn)移1/3。
(R4)設(shè) f是一個(gè)5+-面,v是其關(guān)聯(lián)的真4-點(diǎn),如果v在 f的兩個(gè)相鄰點(diǎn)都是假4-點(diǎn),則 f向v轉(zhuǎn)移7/6;否則,f向v轉(zhuǎn)移1。
(R5)每個(gè)5+-面向其關(guān)聯(lián)的假4-點(diǎn)轉(zhuǎn)移3/4。
設(shè)c*(v)與c*(f)為圖GX中的點(diǎn)v與面 f在執(zhí)行完上述權(quán)轉(zhuǎn)移規(guī)則后的最終權(quán)值。
情況1點(diǎn)v是假4-點(diǎn)
如果點(diǎn)v關(guān)聯(lián)4個(gè)4+-面,則由(R1)與(R5)可知:
如果點(diǎn)v關(guān)聯(lián)3-面,則由于圖G是NIC的,并且其圍長(zhǎng)至少為5,推得點(diǎn)v關(guān)聯(lián)2個(gè)5+-面與1個(gè)4+-面,從而根據(jù)(R1)與(R5)可知:
情況2點(diǎn)v是真4-點(diǎn)
記v1,v2,v3,v4為點(diǎn)v在GX中的4個(gè)鄰點(diǎn),并且f1,f2,f3,f4分別為與{vv1,vv2},{vv2,vv3},{vv3,vv4},{vv4,vv1}關(guān)聯(lián)的面。
如果v在GX中的鄰點(diǎn)都是真點(diǎn),那么由圖G的圍長(zhǎng)至少為5可得點(diǎn)v關(guān)聯(lián)4個(gè)4+-面,從而根據(jù)(R2)與(R4)得到:
如果v在GX中的鄰點(diǎn)有假點(diǎn),則:
(1)當(dāng)v在GX中的鄰點(diǎn)中有且僅有1個(gè)假點(diǎn)時(shí),若點(diǎn) v關(guān)聯(lián)4個(gè)4+-面時(shí),由(R2)與(R4)得式(4)。若點(diǎn)v關(guān)聯(lián)1個(gè)3-面時(shí),則其關(guān)聯(lián)3個(gè)4+-面,且其中1個(gè)是5+-面(否則與圍長(zhǎng)限制條件矛盾),因此根據(jù)(R2)與(R4),可得:
(2)當(dāng)v在GX中的鄰點(diǎn)中有且僅有2個(gè)假點(diǎn)時(shí),根據(jù)對(duì)稱性,考慮兩種子情況。
其一,如果v1,v2是假點(diǎn),則 f1必定為5+-面(否則與NIC-平面圖的定義矛盾),此時(shí)若 f3是5+-面,則根據(jù)(R4)有:
若 f3是4-面,則其必定為假4-面,由(R2)與(R4)得:
其二,如果v1,v3是假點(diǎn),則當(dāng) f1,f2,f3,f4均為4+-面時(shí),由(R2)與(R4)可得式(4)。當(dāng)它們中有至少2個(gè)3-面時(shí),則其中至少有2個(gè)5+-面,故由(R4)得:
當(dāng) f1,f2,f3,f4中有且只有1個(gè)3-面時(shí),則其中有2個(gè)4+-面與1個(gè)5+-面,從而根據(jù)(R2)與(R4)有:
(3)當(dāng)v在GX中的鄰點(diǎn)中有且僅有3個(gè)假點(diǎn)時(shí),不妨設(shè)其為v1,v2,v3,此時(shí)若 f1,f2,f3,f4均為4+-面時(shí),由(R2)與(R4)得式(4)。若 f1,f2,f3,f4中存在3-面時(shí),則其必為 f3或者 f4,不妨設(shè)其為 f4?,F(xiàn) f3為4+-面且f1,f2為5+-面,故由(R2)與(R4)得:
(4)當(dāng)v在GX中的鄰點(diǎn)中有4個(gè)假點(diǎn)時(shí),則其關(guān)聯(lián)4個(gè) 4+-面,從而由(R2)與(R4)得式(4)。
情況3點(diǎn)v是5-點(diǎn)
記v1,v2,v3,v4,v5為點(diǎn)v在GX中的5個(gè)鄰點(diǎn),并且 f1,f2,f3,f4,f5分別為與{vv1,vv2},{vv2,vv3},{vv3,vv4},{vv4,vv5},{vv5,vv1}關(guān)聯(lián)的面。如果 5個(gè)面中至少有3個(gè)4+-面,則根據(jù)(R3)可得:
否則這5個(gè)面中至少有3個(gè)3-面,并且其中2個(gè)必定相鄰。因此不妨設(shè) f1,f2為3-面,由于圖G的圍長(zhǎng)至少為5,故 f1,f2都為假3-面。此時(shí)有兩種情況:其一,當(dāng)v2是假點(diǎn)時(shí),則v1,v3為真點(diǎn),從而vv1v3構(gòu)成了G中的一個(gè)三角形,矛盾;其二,當(dāng)v2是真點(diǎn)時(shí),則v1,v3為假點(diǎn),此時(shí)|θ(v1)?θ(v3)| ≥2,與NIC-平面圖的定義矛盾。
情況4面 f是4-面
由于圖G的圍長(zhǎng)至少為5,故 f是假4-面。再由于圖是NIC-平面的,其恰好關(guān)聯(lián)1個(gè)假4-點(diǎn)。此時(shí)如果 f關(guān)聯(lián)(至少)2個(gè)真4-點(diǎn),其必定關(guān)聯(lián)1個(gè)5+-點(diǎn),并且這2個(gè)真4-點(diǎn)與 f所關(guān)聯(lián)的假4-點(diǎn)相鄰,于是根據(jù)(R1),(R2)與(R3),有:
若 f關(guān)聯(lián)恰好1個(gè)真4-點(diǎn),則由前3條規(guī)則可得:
若 f不關(guān)聯(lián)真4-點(diǎn),則由(R1)與(R3)可得:
情況5面 f是5+-面
當(dāng) d(f)=5時(shí),則根據(jù)(R3)、(R4)與(R5)可知當(dāng) f關(guān)聯(lián)2個(gè)真4-點(diǎn),2個(gè)假4-點(diǎn)與1個(gè)5-點(diǎn)時(shí),f向外轉(zhuǎn)移的權(quán)值最多,從而:
當(dāng)d(f)=d≥6時(shí),設(shè) f關(guān)聯(lián)a個(gè)真4-點(diǎn)與b個(gè)假4-點(diǎn)。因?yàn)檎?-點(diǎn)與真4-點(diǎn)不相鄰并且假4-點(diǎn)與假4-點(diǎn)不相鄰,因此根據(jù)(R3)、(R4)與(R5)可知:
最后,由于6+-點(diǎn)與3-面不參與權(quán)轉(zhuǎn)移,故它們的最終權(quán)值和初始權(quán)值相同,為非負(fù)。
至此,已經(jīng)證明了圖GX中的所有點(diǎn)與面的最終權(quán)值均為非負(fù),即得到:
由于權(quán)只在圖GX中的所有點(diǎn)與面的內(nèi)部進(jìn)行轉(zhuǎn)移,故轉(zhuǎn)移前后的總權(quán)值和不變,即根據(jù)式(3)有:
此與式(5)矛盾。
本章首先給出定理1的一個(gè)重要推論。
推論1設(shè)G是一個(gè)圍長(zhǎng)至少為5的NIC-平面圖,則G存在一個(gè)度數(shù)至多為3的點(diǎn),或者兩個(gè)相鄰的度數(shù)為4的點(diǎn)。
證明 如果圖G不存在度數(shù)至多為3的點(diǎn),則δ(G)≥4。另一方面,由第1章最后一段的分析可知δ(G)≤4,于是δ(G)=4。此時(shí)根據(jù)定理1可知圖G含有兩個(gè)相鄰的度數(shù)為4的點(diǎn)。
設(shè)G是一個(gè)簡(jiǎn)單無(wú)向圖,現(xiàn)將圖G的每一條邊uv進(jìn)行定向(令u指向v或者v指向u)得到一個(gè)有向圖。圖的一個(gè)定向k-染色指的是一個(gè)從V到{1,2,…,k}的映射c,其對(duì)于圖的每一條弧滿足:(1)c(u)≠c(v);(2)不存在弧使得c(x)=c(u)且c(y)=c(v)。從而使得圖具有一個(gè)定向k-染色的最小整數(shù)k稱為圖的定向染色數(shù),記為χo。設(shè)Θ(G)為對(duì)無(wú)向圖G進(jìn)行定向后得到的所有可能的有向圖的集合,則無(wú)向圖G定向染色數(shù)定義為
2007年,Esperet與Ochem[14]證明了如果圖G是不滿足χo(G)≤67的極小反例,則圖G不含有度數(shù)至多為3的點(diǎn),亦不含有兩個(gè)相鄰的度數(shù)為4的點(diǎn)。因此,根據(jù)推論1可得到如下一個(gè)結(jié)果。
定理2設(shè)G是一個(gè)圍長(zhǎng)至少為5的NIC-平面圖,則 χo(G)≤67。
注意到Raspaud與Sopena[15]證明了每個(gè)平面圖G滿足χo(G)≤80,這也是到目前為止最好的結(jié)果。由于NIC-平面圖類包含平面圖類,故從一定的意義上來(lái)看定理2是上述結(jié)論的推廣與改進(jìn)。
綜上所述,本文證明了每個(gè)圍長(zhǎng)至少為5且最小度為4的NIC-平面圖含有一條邊,其2個(gè)頂點(diǎn)的度數(shù)都是4,從而推出每個(gè)圍長(zhǎng)至少為5的NIC-平面圖的定向染色數(shù)至多為67。
定理1中,關(guān)于NIC-平面圖的圍長(zhǎng)的下界5是否可以降低是一個(gè)值得繼續(xù)考慮的問(wèn)題。此外,利用其他方式得到NIC-平面圖的定向染色數(shù)的較好上界也是一個(gè)有意義的研究方向。
參考文獻(xiàn):
[1]Zhang X.Drawing complete multipartite graphs on the plane with restrictions on crossings[J].Acta Mathematica Sinica:English Series,2014,30(12):2045-2053.
[2]Kotzig A.Contribution to the theory of Eulerian polyhedra[J].Mat ?as SAV:Math Slovaca,1955,5:111-113.
[3]Fabrici I,Madaras T.The structure of 1-planar graphs[J].Discrete Mathematics,2007,307:854-865.
[4]Hudák D,?ugerek P.Light edges in 1-planar graphs with prescribed minimum degree[J].Discussiones Mathematicae Graph Theory,2012,32(3):545-556.
[5]田京京,聶玉峰.度限制條件下的IC平面圖類中輕弦4-圈的存在性[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(20):26-28
[6]Zhang X.Light 3-cycles in 1-planar graphs with degree restrictions[J].Bulletin of the Korean Mathematical Society,2014,51(2):511-517.
[7]Tian J,Zhang X,Light triangles in plane graphs with nearindependent crossings[J].Utilitas Mathematica,2015,97:399-405.
[8]Zhang X.A note one the weight of triangle in 1-planar graphs with minimum degree 6[J].Utilitas Mathematica,2014,93:129-134.
[9]Zhang X,Liu G.On the lightness of chordal 4-cycle in 1-planar graphs with high minimum degree[J].Ars Mathematica Contemporanea,2014,7(2):233-243.
[10]Zhang X,Liu G,Wu J.Light subgraphs in the family of 1-planar graphs with high minimum degree[J].Acta Mathematica Sinica:English Series,2012,28(6):1155-1168.
[11]Zhang X,Wu J,Liu G.New upper bounds for the heights of some light subgraphs in 1-planar graphs with high minimum degree[J].Discrete Mathematics and Theoretical Computer Science,2011,13(3):9-16.
[12]張欣,劉桂真,吳建良.1-平面圖的結(jié)構(gòu)性質(zhì)及其在無(wú)圈邊染色上的應(yīng)用[J].中國(guó)科學(xué):數(shù)學(xué),2010,40(10):1025-1032.
[13]Bondy J A,Murty U S R.Graph theory with applications[M].New York:North-Holland,1976.
[14]Esperet L,Ochem P.Oriented colorings of 2-outerplanar graphs[J].Information Processing Letters,2007,101:215-219.
[15]Raspaud A,Sopena E.Good and semi-strong colorings of oriented planar graphs[J].Information Processing Letters,1994,51(4):171-174.