Fullerene圖的L(p，q)-標號問題

董曉媛，馬登舉

(1.南通師范高等專科學校數理系，江蘇 南通 226000；

2.南通大學理學院，江蘇 南通 226007)

?

Fullerene圖的L(p，q)-標號問題

董曉媛1，馬登舉2

(1.南通師范高等專科學校數理系，江蘇 南通 226000；

2.南通大學理學院，江蘇 南通 226007)

[摘要]主要研究了一類Fullerene圖Fspan的L(2，1)-標號問題及L(1，1)-標號問題，給出了Fspan的L(2，1)-標號數和L(1，1)-標號數的上界分別為7和6.該結果驗證了Georges和Mauro猜想與Wegner猜想對于Fullerene圖Fspan均成立.

[關鍵詞]L(p，q)-標號，Fullerene圖

1預備知識

Fullerene圖是一類3-正則3-連通的平面圖，且其在平面上的一個嵌入中每個面的邊界是5-圈或6-圈.[1-4]

定義圖Fm如下：它的頂點集為

邊集為

由Fm的定義知，Fm是一類3-正則圖，且有m+2個圈，分別為：

(1) 當i=0時，有一個含5個頂點的圈：

C0=u0，1u0，2u0，3u0，4u0，5；

(2) 當i=1，2，…，m時，有一個含10個頂點的圈：

Ci=ui，1ui，2…ui，10ui，1；

(3) 當i=m+1時，有一個含5個頂點的圈：

Cm+1=um+1，1um+1，2um+1，3um+1，4um+1，5.

按照m的奇偶性，Fm的一個平面嵌入如圖1與圖2所示.易見：Fm是一個3-連通的圖，且每個圈的邊界是5-圈或6-圈.因此Fm是一類Fullerene圖.

圖1　當m為奇數時，Fullerene圖Fm在平面上的一種嵌入

圖2　當m為偶數時，Fullerene圖Fm在平面上的一種嵌入

一個圖G的L(p，q)-標號，是一個從G的頂點集V(G)到一個非負整數集的一個映射f，使得對G中的任意兩個頂點u，v，當d(u,v)=1時，|f(u)-f(v)|≥p；當d(u,v)=2時，|f(u)-f(v)|≥q.這里d(u,v)表示u,v的距離.

一個圖G的平方圖G2是這樣一個圖，它的頂點集與G的頂點集相同，兩個頂點相鄰，當且僅當這兩個頂點在G中的距離不大于2.

本文我們主要研究Fullerene圖Fm的L(2，1)-標號問題與L(1，1)-標號問題.

2Fullerene圖的L(2，1)-標號

定理1圖Fm的L(2，1)-標號數λ2，1(Fm)≤7.

證明當m>10時，定義Fullerene圖Fm的一個標號f如下：

f(u0，1)=7，f(u0，2)=1，f(u0，3)=6，f(u0，4)=3，f(u0，5)=0；

f(ui，1)=4，f(ui，2)=0，f(ui，3)=3，f(ui，4)=7，f(ui，5)=2，

f(ui，6)=5，f(ui，7)=7，f(ui，8)=4，f(ui，9)=6，f(ui，10)=1，i≡1(mod10)；

f(ui，1)=4，f(ui，2)=6，f(ui，3)=1，f(ui，4)=4，f(ui，5)=0，

f(ui，6)=3，f(ui，7)=7，f(ui，8)=2，f(ui，9)=5，f(ui，10)=7，i≡2(mod10)；

f(ui，1)=2，f(ui，2)=5，f(ui，3)=7，f(ui，4)=4，f(ui，5)=6，

f(ui，6)=1，f(ui，7)=4，f(ui，8)=0，f(ui，9)=3，f(ui，10)=7，i≡3(mod10)；

f(ui，1)=0，f(ui，2)=3，f(ui，3)=7，f(ui，4)=2，f(ui，5)=5，

f(ui，6)=7，f(ui，7)=4，f(ui，8)=6，f(ui，9)=1，f(ui，10)=4，i≡4(mod10)；

f(ui，1)=6，f(ui，2)=1，f(ui，3)=4，f(ui，4)=0，f(ui，5)=3，

f(ui，6)=7，f(ui，7)=2，f(ui，8)=5，f(ui，9)=7，f(ui，10)=4，i≡5(mod10)；

f(ui，1)=5，f(ui，2)=7，f(ui，3)=4，f(ui，4)=6，f(ui，5)=1，

f(ui，6)=4，f(ui，7)=0，f(ui，8)=3，f(ui，9)=7，f(ui，10)=2，i≡6(mod10)；

f(ui，1)=3，f(ui，2)=7，f(ui，3)=2，f(ui，4)=5，f(ui，5)=7，

f(ui，6)=4，f(ui，7)=6，f(ui，8)=1，f(ui，9)=4，f(ui，10)=0，i≡7(mod10)；

f(ui，1)=1，f(ui，2)=4，f(ui，3)=0，f(ui，4)=3，f(ui，5)=7，

f(ui，6)=2，f(ui，7)=5，f(ui，8)=7，f(ui，9)=4，f(ui，10)=6，i≡8(mod10)；

f(ui，1)=7，f(ui，2)=4，f(ui，3)=6，f(ui，4)=1，f(ui，5)=4，

f(ui，6)=0，f(ui，7)=3，f(ui，8)=7，f(ui，9)=2，f(ui，10)=5，i≡9(mod10)；

f(ui，1)=7，f(ui，2)=2，f(ui，3)=5，f(ui，4)=7，f(ui，5)=4，

f(ui，6)=6，f(ui，7)=1，f(ui，8)=4，f(ui，9)=0，f(ui，10)=3，i≡0(mod10).

對于Fullerene圖Fm，當m>10時，從F1到F10的L(2，1)-標號以及定義可知：第0圈u0，1，u0，2，u1，3，…，u0，5總是依次標為7，1，6，3，0；第1圈u1，1，u1，2，u1，3，…，u1，9，u1，10依次標為4，0，3，7，2，5，7，4，6，1；第2圈u2，1，u2，2，u2，3，…，u2，9，u2，10依次標為4，6，1，4，0，3，7，2，5，7；照此類推，到第11圈的時候開始與第1圈重復標號，依次為4，0，3，7，2，5，7，4，6，1；第12圈與第2圈重復標號，依次為4，6，1，4，0，3，7，2，5，7；….也就是說，對于Fm，當m>10且m≡imod10，i=0，1，2，…，9時，Fm的第0圈與Fi的第0圈各頂點標號相同，Fm的第m圈與Fi的第i圈各頂點標號相同，Fm的第m+1圈與Fi的第i+1圈各頂點標號相同.而Fm的第1至m-1圈總是標4，0，3，7，2，5，7，4，6，1這10個數(順序與F10相同).即Fm與Fi的L(2，1)-標號數相同.

這樣，上面定義的Fullerene圖的標號f是一個7-L(2，1)-標號.因此，Fullerene圖的L(2，1)-標號數λ2，1(Fm)≤7.定理證畢.

1992年，Griggs和Yeh得到最大度為Δ的圖G的L(2，1)-標號數的下界：

引理1[5]圖G包含三個最大度Δ≥2的頂點，且其中一個頂點與另兩個頂點相鄰，則λ2，1(G)≥Δ+2.

由引理1可知λ2，1(Fm)≥5.

綜上，Fm的L(2，1)-標號數5≤λ2，1(Fm)≤7.

2002年，Georges和Mauro[6]提出一個猜想：Petersen圖是唯一一個L(2，1)-標號數為9的3-正則圖，其他的3-正則圖的L(2，1)-標號數總是至多為8.我們發現，對Fullerene圖Fm這個猜想成立.

3Fullerene圖的L(1，1)-標號

定理2Fm的L(1，1)-標號數λ1，1(Fm)≤6.

證明當m>10時，定義Fullerene圖Fm的一個標號f如下：

f(u0，1)=1，f(u0，2)=0，f(u0，3)=3，f(u0，4)=2，f(u0，5)=5；

f(ui，1)=3，f(ui，2)=4，f(ui，3)=2，f(ui，4)=1，f(ui，5)=5，

f(ui，6)=0，f(ui，7)=4，f(ui，8)=3，f(ui，9)=0，f(ui，10)=6，i≡1(mod10)；

f(ui，1)=3，f(ui，2)=0，f(ui，3)=6，f(ui，4)=3，f(ui，5)=4，

f(ui，6)=2，f(ui，7)=1，f(ui，8)=5，f(ui，9)=0，f(ui，10)=4，i≡2(mod10)；

f(ui，1)=5，f(ui，2)=0，f(ui，3)=4，f(ui，4)=3，f(ui，5)=0，

f(ui，6)=6，f(ui，7)=3，f(ui，8)=4，f(ui，9)=2，f(ui，10)=1，i≡3(mod10)；

f(ui，1)=4，f(ui，2)=2，f(ui，3)=1，f(ui，4)=5，f(ui，5)=0，

f(ui，6)=4，f(ui，7)=3，f(ui，8)=0，f(ui，9)=6，f(ui，10)=3，i≡4(mod10)；

f(ui，1)=0，f(ui，2)=6，f(ui，3)=3，f(ui，4)=4，f(ui，5)=2，

f(ui，6)=1，f(ui，7)=5，f(ui，8)=0，f(ui，9)=4，f(ui，10)=3，i≡5(mod10)；

f(ui，1)=0，f(ui，2)=4，f(ui，3)=3，f(ui，4)=0，f(ui，5)=6，

f(ui，6)=3，f(ui，7)=4，f(ui，8)=2，f(ui，9)=1，f(ui，10)=5，i≡6(mod10)；

f(ui，1)=2，f(ui，2)=1，f(ui，3)=5，f(ui，4)=0，f(ui，5)=4，

f(ui，6)=3，f(ui，7)=0，f(ui，8)=6，f(ui，9)=3，f(ui，10)=4，i≡7(mod10)；

f(ui，1)=6，f(ui，2)=3，f(ui，3)=4，f(ui，4)=2，f(ui，5)=1，

f(ui，6)=5，f(ui，7)=0，f(ui，8)=4，f(ui，9)=3，f(ui，10)=0，i≡8(mod10)；

f(ui，1)=4，f(ui，2)=3，f(ui，3)=0，f(ui，4)=6，f(ui，5)=3，

f(ui，6)=4，f(ui，7)=2，f(ui，8)=1，f(ui，9)=5，f(ui，10)=0，i≡9(mod10)；

f(ui，1)=1，f(ui，2)=5，f(ui，3)=0，f(ui，4)=4，f(ui，5)=3，

f(ui，6)=0，f(ui，7)=6，f(ui，8)=3，f(ui，9)=4，f(ui，10)=2，i≡0(mod10).

對于Fullerene圖Fm，當m>10時，從F1到F10的L(1，1)-標號以及定義可知：第0圈u0，1，u0，2，u1，3，…，u0，5總是依次標為1，0，3，2，5；第1圈u1，1，u1，2，u1，3，…，u1，9，u1，10依次標為3，4，2，1，5，0，4，3，0，6；第2圈u2，1，u2，2，u2，3，…，u2，9，u2，10依次標為3，0，6，3，4，2，1，5，0，4；依此類推，到第11圈的時候開始與第1圈重復標號，依次為3，4，2，1，5，0，4，3，0，6；第12圈與第2圈重復標號，依次為3，0，6，3，4，2，1，5，0，4；….也就是說，對于Fm，當m>10且m≡i(mod10)，i=0，1，2，…，9時，Fm的第0圈與Fi的第0圈各頂點標號相同，Fm的第m圈與Fi的第i圈各頂點標號相同，Fm的第m+1圈與Fi的第i+1圈各頂點標號相同.而Fm的第1至m-1圈總是標3，4，2，1，5，0，4，3，0，6這10個數(順序與F10相同).即Fm與Fi的L(1，1)-標號數相同.

這樣，上面定義的Fullerene圖Fm的標號f是一個6-L(1，1)-標號.從而λ1，1(Fm)≤6.定理證畢.

由圖的色數及圖的L(p，q)-標號的定義，可知圖G的平方圖的色數χ(G2)與G的L(1，1)-標號數有關，從而我們得出如下結論：

推論1Fm的平方圖的色數χ(Fm2)=λ1，1(Fm)+1≤7.

在1977年，Wegner[7]曾猜想一個最大度為3的平面圖G的平方圖G2的色數χ(G2)≤7.我們的結果表明，對Fullerene圖Fm，該猜想成立.

[參考文獻]

[1]DOSLIC T. On lower bounds of number of perfect matchings in Fullerene graphs [J]. Mathematical Chemistry，1998，24:359-364.

[2]KARDOS F，KRAL D，MISKUF J. Fullerene graphs have exponentially many perfect matchings [J]. Mathematical Chemistry，2009，46:443-477.

[3]BUHL M，HIRSCH A. Spherical aromaticity of Fullerene [J]. Chem Rev，2001，101：1153-1183.

[4]馬海成，汪小玲. 點圈并圖的匹配等價圈數[J].東北師大學報(自然科學版)，2006，38(4)：36-40.

[5]GRIGGS J R，YEH R.K. Labeling graphs with a condition at distance two [J]. SIAM J Discrete Mathematics，1992(5)：586-595.

[6]GEORGES J P，MAURO D W. On generalized Petersen graphs labeled with a condition at distance two[J]. SIAM J Discrete Mathematics，2002，259:311-318.

[7]WEGNER G. Graphs with given diameter and a coloring problem[R] Germany：University of Dortmund，1977.

(責任編輯：李亞軍)

L(p，q)-labeling of the Fullerene graphs

DONG Xiao-yuan1，MA Deng-ju2

(1.Department of Mathematics and Physics，Nantong Normal College，Nantong 226000，China；2.School of Science，Nantong University，Nantong 226007，China)

Abstract:The L(2，1)-labeling and L(1，1)-labeling of the Fullerene graph Fspanare studied. It is proved that the L(2，1)-labeling number and the L(1，1)-labeling number of Fspanare at most 7 and 6 respectively，which verify the correction of the guesses presented by Georges and Wegner respectively.

Keywords:L(p，q)-labeling；Fullerene graph

[中圖分類號]O 157.5[學科代碼]110·7470

[文獻標志碼]A

[作者簡介]董曉媛(1984—)，女，碩士，講師，主要從事圖的染色問題及其應用研究；通訊作者：馬登舉(1968—)，男，博士，副教授，主要從事圖的染色問題及其應用研究.

[基金項目]國家自然科學基金資助項目(11171114).

[收稿日期]2014-06-12

[文章編號]1000-1832(2016)01-0014-04

[DOI]10.16163/j.cnki.22-1123/n.2016.01.004