陳 東

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

圖的(2,1)-點面標號*1

陳 東

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

圖;距離2標號;(2,1)-點面標號;外平面圖

0 引 言

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

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

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

設(shè)c是圖G的一個k-(2,1)-點面標號.對于任意的元素x∈V∪F,定義c′(x)=k-c(x).顯然,c′也是圖G的一個k-(2,1)-點面標號,于是稱c和c′為對稱標號.

根據(jù)定義1,很容易得到一個平面圖G的(2,1)-點面標號數(shù)的平凡上下界

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

1 一些簡單圖類的(2,1)-點面標號

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

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

引理1設(shè)c是2-連通圖G的一個5-(2,1)-點面標號,那么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-邊.

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

接下來直接給出K4的一個6-(2,1)-點面標號,如圖1所示.

圖1 K4的一個6-(2,1)-點面標號

為方面敘述,定義

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

2 外平面圖的(2,1)-點面標號

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3)重復2),直到G的每個點都有標號.

至此,每條內(nèi)邊所對應(yīng)的點的標號都是0和1,奇內(nèi)面至少有一個2-點標號為2,偶內(nèi)面所有點的標號都是0和1.

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

因為任意2個奇內(nèi)面的距離都是偶數(shù),所以由引理2可以確定這種標號分配方式是合理的.

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

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

圖2 G和G的極大開子圖

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

1)每個極大開子圖點的標號集為{0,1,2},只有2-點的標號可能為2,度數(shù)至少為3的點的標號一定是0或者1;

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

3)每個極大開子圖的外面標號為5.

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

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

另一方面,因為Guv是一個2-連通的開外平面圖,并且Guv中有奇內(nèi)面f1,由引理3及c(f2)∈{4,5}可知,f1上一定有標號為 2的點.那么,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.

(責任編輯 陶立方)

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

國家自然科學基金資助項目(11401535)

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

O157.5

A

1001-5051(2015)02-0148-08