圖的(2,1)-點(diǎn)面標(biāo)號(hào)*1

陳 東

(浙江師范大學(xué) 行知學(xué)院,浙江 金華 321004)

圖的(2,1)-點(diǎn)面標(biāo)號(hào)*1

陳 東

(浙江師范大學(xué) 行知學(xué)院,浙江 金華 321004)

圖;距離2標(biāo)號(hào);(2,1)-點(diǎn)面標(biāo)號(hào);外平面圖

0 引 言

著名的距離 2 標(biāo)號(hào)問題源于這樣的一個(gè)無線電頻道分配問題:給一個(gè)無線電網(wǎng)絡(luò)中的發(fā)射站分配頻道,為了避免干擾,要求相鄰的發(fā)射站使用的無線電頻道差值至少為2,同時(shí)要求距離為2的2個(gè)發(fā)射站使用不同的頻道.該問題也被稱為L(zhǎng)(2,1)-標(biāo)號(hào)問題.1992年,Griggs等[1]首先提出并研究了圖的L(2,1)-標(biāo)號(hào)問題.此后,這個(gè)概念被國內(nèi)外同行廣泛研究,詳見文獻(xiàn)[2-7].

把一個(gè)平面圖看作是一個(gè)無線電網(wǎng)絡(luò),并為網(wǎng)絡(luò)中的所有發(fā)射站分配無線電頻率:在平面圖上的每個(gè)頂點(diǎn)處設(shè)置一個(gè)發(fā)射站,要求圖上相鄰2個(gè)頂點(diǎn)所對(duì)應(yīng)的發(fā)射站使用不同的頻道;并在圖上的每個(gè)面內(nèi)設(shè)置一個(gè)發(fā)射站,要求圖上相鄰2個(gè)面所對(duì)應(yīng)的發(fā)射站使用不同的頻道;此外,為了避免干擾,要求圖上每個(gè)頂點(diǎn)及其所在面所對(duì)應(yīng)的發(fā)射站使用的頻道差值至少為2.

為解決上述問題,可以構(gòu)建如下數(shù)學(xué)模型:設(shè)G是一個(gè)可平面圖,G(V,E,F)是G在平面上的一個(gè)嵌入,其中V,E,F分別代表G的頂點(diǎn)集合、邊集合及面集合.

設(shè)c是圖G的一個(gè)k-(2,1)-點(diǎn)面標(biāo)號(hào).對(duì)于任意的元素x∈V∪F,定義c′(x)=k-c(x).顯然,c′也是圖G的一個(gè)k-(2,1)-點(diǎn)面標(biāo)號(hào),于是稱c和c′為對(duì)稱標(biāo)號(hào).

根據(jù)定義1,很容易得到一個(gè)平面圖G的(2,1)-點(diǎn)面標(biāo)號(hào)數(shù)的平凡上下界

本文首先研究了一些簡(jiǎn)單圖類的(2,1)-點(diǎn)面標(biāo)號(hào)問題,給出了樹、圈、歐拉二部圖、K4、外平面圖等圖類的(2,1)-點(diǎn)面標(biāo)號(hào)數(shù)的上界.此外,重點(diǎn)討論了外平面圖的(2,1)-點(diǎn)面標(biāo)號(hào)問題,完全刻畫了至多含有一個(gè)閉內(nèi)面的外平面圖的(2,1)-點(diǎn)面標(biāo)號(hào)數(shù).

1 一些簡(jiǎn)單圖類的(2,1)-點(diǎn)面標(biāo)號(hào)

若無特殊說明,本文只考慮簡(jiǎn)單的平面圖,并且直接使用G表示它在平面上的嵌入.對(duì)于一個(gè)面及其邊界路上的點(diǎn)和邊,稱這三者是兩兩關(guān)聯(lián)的.一個(gè)面的度定義為該面上邊界路中出現(xiàn)的邊的數(shù)量.若f的度是奇數(shù),則稱f為奇面,否則稱為偶面.下面將給出幾個(gè)簡(jiǎn)單圖類的(2,1)-點(diǎn)面標(biāo)號(hào)數(shù)的上界.

設(shè)c是圖G的一個(gè)(2,1)-點(diǎn)面標(biāo)號(hào),uv是G中的一條邊.若{c(u),c(v)}={a,b},為方便敘述,則可將uv稱為一條(a,b)e-邊.

引理1設(shè)c是2-連通圖G的一個(gè)5-(2,1)-點(diǎn)面標(biāo)號(hào),那么G中只可能有(0,1)e-邊,(0,2)e-邊,(0,5)e-邊,(1,2)e-邊,(2,3)e-邊,(3,4)e-邊,(3,5)e-邊及(4,5)e-邊.

證明 因?yàn)镚是2-連通圖,所以每條邊至少關(guān)聯(lián)2個(gè)面.注意到,c所使用的標(biāo)號(hào)集合為{0,1,2,3,4,5}.如果G中有(0,3)e-邊,那么該邊關(guān)聯(lián)的2個(gè)面無法正常標(biāo)號(hào),這是一個(gè)矛盾.對(duì)于其他的邊,同理可以推出矛盾.引理1證畢.

接下來直接給出K4的一個(gè)6-(2,1)-點(diǎn)面標(biāo)號(hào),如圖1所示.

圖1 K4的一個(gè)6-(2,1)-點(diǎn)面標(biāo)號(hào)

為方面敘述,定義

Fabc={f∈F(K4)|f關(guān)聯(lián)的3個(gè)點(diǎn)的標(biāo)號(hào)分別為a,b,c}.

2 外平面圖的(2,1)-點(diǎn)面標(biāo)號(hào)

設(shè)G是一個(gè)外平面圖,令f0是G的外面.若G的某一個(gè)內(nèi)面全是由內(nèi)邊組成,則稱其為閉內(nèi)面,反之為開內(nèi)面.若一個(gè)外平面圖不存在閉內(nèi)面,則稱其為開外平面圖.另外,定義G的內(nèi)面對(duì)偶圖G*如下:把G的每一個(gè)內(nèi)面看作是G*的一個(gè)點(diǎn),G*中2個(gè)點(diǎn)有邊連接當(dāng)且僅當(dāng)它們?cè)贕中對(duì)應(yīng)的內(nèi)面有公共邊,同時(shí)刪除重邊使得G*是一個(gè)簡(jiǎn)單圖.

引理2設(shè)G是一個(gè)連通的外平面圖,如果G*是G的內(nèi)面對(duì)偶圖,那么G*是一個(gè)森林.

設(shè)f1,f2是外平面圖G的2個(gè)內(nèi)面,把f1與f2在G*中對(duì)應(yīng)點(diǎn)間的距離定義為G中這2個(gè)內(nèi)面f1與f2之間的距離,記為d(f1,f2).由引理2可知,G的任意2個(gè)內(nèi)面之間的距離是唯一的.

因?yàn)镚是外平面圖,所以G的點(diǎn)色數(shù)是3,因此,可以對(duì)G中的點(diǎn)使用標(biāo)號(hào)0,1,2.根據(jù)引理2,G的內(nèi)面對(duì)偶圖是樹,那么可以為G的所有內(nèi)面指定標(biāo)號(hào)4和5.最后,令G的外面的標(biāo)號(hào)為6.這樣,就得到了G的一個(gè)6-(2,1)-點(diǎn)面標(biāo)號(hào).定理6證畢.

根據(jù)定理6,一個(gè)2-連通外平面圖的(2,1)-點(diǎn)面標(biāo)號(hào)數(shù)只有3種可能:4,5或6.再根據(jù)定理3,當(dāng)2-連通外平面圖不是歐拉二部圖時(shí),其(2,1)-點(diǎn)面標(biāo)號(hào)數(shù)不是5就是6.那么,尋找2-連通外平面圖(2,1)-點(diǎn)面標(biāo)號(hào)數(shù)的刻畫條件就變得非常有意義.

引理3設(shè)G是一個(gè)2-連通外平面圖,并且G含有一個(gè)奇內(nèi)面f1.如果G有一個(gè)5-(2,1)-點(diǎn)面標(biāo)號(hào)c,那么f1上一定有標(biāo)號(hào)為2或3的點(diǎn);如果G還是一個(gè)2-連通開外平面圖,那么G的點(diǎn)標(biāo)號(hào)集合一定是{0,1,2}或{3,4,5},對(duì)應(yīng)的面標(biāo)號(hào)集合一定是{3,4,5}或{0,1,2}.

證明 利用反證法,首先假設(shè)f1上沒有標(biāo)號(hào)為2或3的點(diǎn).注意到,c所使用的標(biāo)號(hào)集合為{0,1,2,3,4,5}.根據(jù)標(biāo)號(hào)的對(duì)稱性,對(duì)于f1上任意的一條邊e,e只可能為(0,1)e-邊,(0,4)e-邊,(0,5)e-邊和(1,4)e-邊,但是這些可能性都與引理1矛盾.根據(jù)e的任意性,奇面f1中的點(diǎn)標(biāo)號(hào)都是0或1.事實(shí)上,奇面上的點(diǎn)至少需要3個(gè)標(biāo)號(hào),這是一個(gè)矛盾.因此,f1上一定有標(biāo)號(hào)為 2 或 3 的點(diǎn).

下面考慮當(dāng)G是一個(gè)2-連通開外平面圖時(shí)的情況.假設(shè)G中點(diǎn)的標(biāo)號(hào)集合既不是{0,1,2},也不是{3,4,5}.根據(jù)之前的討論及標(biāo)號(hào)的對(duì)稱性,不妨設(shè)f1中的點(diǎn)u的標(biāo)號(hào)為2.顯然,f1上不存在標(biāo)號(hào)為4或者5的點(diǎn),否則f1和外面f0必須使用同一個(gè)標(biāo)號(hào)0,這是一個(gè)矛盾.于是,假設(shè)f1上存在點(diǎn)v使得c(v)=3,那么{c(f1),c(f2)}={0,5}.進(jìn)而推知,f1上的點(diǎn)的標(biāo)號(hào)只能是2或者3,這與奇圈f1上的點(diǎn)至少需要3個(gè)標(biāo)號(hào)矛盾.因此,f1上的點(diǎn)標(biāo)號(hào)集合是{0,1,2},并且標(biāo)號(hào)集合中的每個(gè)標(biāo)號(hào)都會(huì)被用到.容易推斷,G中其他點(diǎn)的標(biāo)號(hào)也只能來自于{0,1,2},否則會(huì)造成外面f0無標(biāo)號(hào)可用.引理3證畢.

1)假設(shè)G存在一個(gè)無2-點(diǎn)的奇內(nèi)面f1.根據(jù)引理3及標(biāo)號(hào)的對(duì)稱性,不妨設(shè)f1上有個(gè)點(diǎn)u使得c(u)=2.又因?yàn)閒1上沒有2-點(diǎn),所以d(u)≥3.于是,假設(shè)uv是f1關(guān)聯(lián)的一條內(nèi)邊,f2是uv關(guān)聯(lián)的另一個(gè)內(nèi)面.因?yàn)閏(u)=2,所以c(f0),c(f1),c(f2)∈{0,4,5}.又因?yàn)镚是一個(gè)開外平面圖,所以f0,f1,f2兩兩相鄰,也就是說,它們的標(biāo)號(hào)必須兩兩不同.因此,{c(f0),c(f1),c(f2)}={0,4,5}.但是,標(biāo)號(hào)為0和4的這2個(gè)面是相鄰的,這會(huì)導(dǎo)致這2個(gè)面公共邊上的2個(gè)頂點(diǎn)無標(biāo)號(hào)可用,矛盾.

2)假設(shè)G存在2個(gè)距離為奇數(shù)的奇內(nèi)面f1和f2.根據(jù)引理3及標(biāo)號(hào)的對(duì)稱性,不妨設(shè)G的每一個(gè)奇內(nèi)面上有點(diǎn)標(biāo)2,并且G的點(diǎn)標(biāo)號(hào)集為{0,1,2},那么奇面與外面f0的標(biāo)號(hào)集合就是{4,5},偶面的標(biāo)號(hào)集合就是{3,4,5}.設(shè)c(f0)=a∈{4,5},則G中所有奇面的標(biāo)號(hào)都是b={4,5}{a}.因?yàn)镚是開外平面圖,每個(gè)內(nèi)面都與外面相鄰,所以內(nèi)面可用的標(biāo)號(hào)集就是{3,b}.根據(jù)引理2,G的內(nèi)面標(biāo)號(hào)一定是3和b交替分布.也就是說,奇面f1和f2之間的距離應(yīng)該是偶數(shù),這與假設(shè)矛盾.

1)任意選擇G的一個(gè)終端面,并為這個(gè)終端面及其關(guān)聯(lián)的點(diǎn)分配標(biāo)號(hào).

易知,這樣的終端面是存在的,并且這個(gè)終端面一定是由一條內(nèi)邊e=uv及一條除端點(diǎn)u,v外都是2-點(diǎn)的路P圍成.首先,令u和v的標(biāo)號(hào)分別為0和1.然后,除u,v外,如果P中還有偶數(shù)個(gè)點(diǎn),那么對(duì)它們依次使用標(biāo)號(hào)0和1;如果還有奇數(shù)個(gè)點(diǎn),那么可以使用0,1和2為這些點(diǎn)標(biāo)號(hào).容易驗(yàn)證,這種標(biāo)號(hào)分配方式是合理的,并且唯一的內(nèi)邊e的2個(gè)端點(diǎn)的標(biāo)號(hào)為0和1.

2)任意選取一個(gè)只有一條獲得標(biāo)號(hào)的內(nèi)邊且其標(biāo)號(hào)是0和1的內(nèi)面,并對(duì)這個(gè)面及其關(guān)聯(lián)的點(diǎn)標(biāo)號(hào).

如果這個(gè)內(nèi)面是偶面,那么按照已有的標(biāo)號(hào)順序,為剩下的點(diǎn)依次分配標(biāo)號(hào)0和1;如果這個(gè)內(nèi)面是奇面,那么按照已有的標(biāo)號(hào)順序,為剩下的同時(shí)屬于內(nèi)邊的點(diǎn)(一定恰好就是該面中度數(shù)至少為3的點(diǎn))依次分配標(biāo)號(hào)0和1.因?yàn)槊總€(gè)奇內(nèi)面都有2-點(diǎn),所以可以為剩下的2-點(diǎn)依次分配標(biāo)號(hào)0,1和2.容易驗(yàn)證,這種標(biāo)號(hào)分配方式也是合理的,并且每條內(nèi)邊的2個(gè)端點(diǎn)的標(biāo)號(hào)為0和1.

3)重復(fù)2),直到G的每個(gè)點(diǎn)都有標(biāo)號(hào).

至此,每條內(nèi)邊所對(duì)應(yīng)的點(diǎn)的標(biāo)號(hào)都是0和1,奇內(nèi)面至少有一個(gè)2-點(diǎn)標(biāo)號(hào)為2,偶內(nèi)面所有點(diǎn)的標(biāo)號(hào)都是0和1.

4)令外面的標(biāo)號(hào)為5,奇內(nèi)面的標(biāo)號(hào)為4,其他內(nèi)面的標(biāo)號(hào)用3和4交替分配.

因?yàn)槿我?個(gè)奇內(nèi)面的距離都是偶數(shù),所以由引理2可以確定這種標(biāo)號(hào)分配方式是合理的.

注1根據(jù)定理7必要性的證明可以發(fā)現(xiàn)如下事實(shí):一個(gè)好的2-連通開外平面圖G,一定存在著一個(gè)5-(2,1)-點(diǎn)面標(biāo)號(hào)使得下列命題成立:1)G中的點(diǎn)的標(biāo)號(hào)集為{0,1,2},只有2-點(diǎn)的標(biāo)號(hào)可能為2,度數(shù)至少為3的點(diǎn)的標(biāo)號(hào)一定是0或者1;2)G中內(nèi)面的標(biāo)號(hào)集為{3,4},奇內(nèi)面的標(biāo)號(hào)一定為4;3)G的外面標(biāo)號(hào)為5.

例1如圖2(a)所示,G是一個(gè)2-連通外平面圖,v1,v4,v10構(gòu)成的G的唯一閉內(nèi)面.圖2(b)中3個(gè)部分按順時(shí)針順序分別是G的v1v4-極大開子圖Gv1v4,v4v10-極大開子圖Gv4v10及v10v1-極大開子圖Gv10v1.

圖2 G和G的極大開子圖

證明 由于G的每個(gè)極大開子圖都是一個(gè)2-連通的開外平面圖,所以根據(jù)定理6和定理7,充分性顯然成立.對(duì)于命題的必要性,使用反證法,只要證明:當(dāng)G的每一個(gè)極大開子圖都是好的,G卻存在一個(gè)5-(2,1)-點(diǎn)面標(biāo)號(hào).

1)每個(gè)極大開子圖點(diǎn)的標(biāo)號(hào)集為{0,1,2},只有2-點(diǎn)的標(biāo)號(hào)可能為2,度數(shù)至少為3的點(diǎn)的標(biāo)號(hào)一定是0或者1;

2)每個(gè)極大開子圖中內(nèi)面的標(biāo)號(hào)集為{3,4},奇內(nèi)面的標(biāo)號(hào)一定為4;

3)每個(gè)極大開子圖的外面標(biāo)號(hào)為5.

必要性 使用反證法,只需證明G在下述3種不同情況下都不存在5-(2,1)-點(diǎn)面標(biāo)號(hào)即可:

1)G有一個(gè)極大開子圖Guv是壞的.

另一方面,因?yàn)镚uv是一個(gè)2-連通的開外平面圖,并且Guv中有奇內(nèi)面f1,由引理3及c(f2)∈{4,5}可知,f1上一定有標(biāo)號(hào)為 2的點(diǎn).那么,c(f1),c(f0)∈{4,5}并且c(f1)≠c(f0).

[1]Griggs J R,Yeh R K.Labelling graphs with a condition at distance two[J].SIAM J Discrete Math,1992,5(4):586-595.

[2]Chang G J,Guo D.TheL(2,1)-labelling problem on graphs[J].SIAM J Discrete Math,1996,9(2):309-316.

[3]Borodin O V.A new proof of the 6 color theorem[J].J Graph Theory,1995,19(4):507-521.

[4]Sakai D.Labelling chordal graphs: distance two condition[J].SIAM J Discrete Math,1994,7(1):133-140.

[5]Wang Weifan,Liu Jiazhuang.On the vertex face total chromatic number of planar graphs[J].J Graph Theory,1996,22(1):29-37.

[6]Wang Weifan,Lih K W.Labelling planar graphs with conditions on girth and distance two[J].SIAM J Discrete Math,2004,17(2):264-275.

[7]Zhu Haiyang,Hou Lifeng,Chen Wei,et al.TheL(p,q)-labelling of planar graphs without 4-cycles[J].Discrete Appl Math,2014,162(1):355-363.

(責(zé)任編輯 陶立方)

The(2,1)-totallabellingoftheproductoftwokindsofgraphs

CHEN Dong

(XingzhiCollege,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

Ak-(2,1)-coupled labelling of a plane graphGwas defined as a mapping fromV(G)∪F(G) to {0,1,…,k} such that adjacent vertices or adjacent faces

different numbers, and numbers of the vertex and the face incidentally received differed by at least 2. The (2,1)-coupled labelling numberλvf2(G) ofGwas defined as the smallest integerksuch thatGhad ak-(2,1)-coupled labelling. A tight upper bounds of (2,1)-total labelling number were given for trees, cycles,K4, Eulerian bipartite graphs, outerplanar graphs, etc. In addition, a complete characterization of (2,1)-coupled labelling numbers for outerplanar graphs with at most one closed inner face was presented.

graph; distance two labelling; (2,1)-coupled labelling; outerplanar graph

10.16218/j.issn.1001-5051.2015.02.005

2015-03-21

國家自然科學(xué)基金資助項(xiàng)目(11401535)

陳 東(1981-),男，浙江金華人，講師.研究方向：圖論與組合數(shù)學(xué).>

O157.5

A

1001-5051(2015)02-0148-08