一類聯(lián)圖的性質(zhì)和標號研究

嚴謙泰

(安陽師范學院 數(shù)學與統(tǒng)計學院，河南 安陽 455000)

1 研究背景

優(yōu)美圖由于其有趣性及較好的應(yīng)用價值和研究前景，研究十分活躍。最近十幾年來，國內(nèi)外取得不少優(yōu)美圖的研究成果[1]，它們也被用于許多領(lǐng)域。優(yōu)美圖的研究始于1963年Ringel的一個猜想[2]，1972年Golomb明確給出了優(yōu)美圖的定義[3]。之后，Gallian又提出了每棵樹都是奇優(yōu)美的[4]，開始了奇優(yōu)美圖的研究。但由于缺少系統(tǒng)和有力的工具，至今只能對一些特殊圖類研究其奇優(yōu)美性[5]。圖的強協(xié)調(diào)標號問題是圖論中的一個十分有趣的研究課題,自1982年Frank引入圖的強協(xié)調(diào)標號[6]，已有許多這方面的結(jié)果[7]。但對于積圖討論以上兩種標號的結(jié)果很少。

定義1[2]對于簡單圖G=，如果存在一個映射f:V(G)→{0,1,2,…,|E|}，滿足1)對任意的u,v∈V，若u≠v,則f(u)≠f(v);2)max{f(v)|v∈V}=|E|;3)對任意的e1,e2∈E,若e1≠e2,則g(e1)≠g(e2),此處g(e)=|f(u)-f(v)|,e=uv；4){g(e)|e∈E}={1,2,…,|E|},則稱G為優(yōu)美圖，f為G的優(yōu)美標號。

定義2[8]設(shè)G=是一個無向簡單圖。如果存在一個映射f：V(G)→{0,1,2,…,|E|}，滿足：1)f是單射;2)?uv∈E(G),令f(uv)=f(u)+f(v)，有{f(uv)∣uv∈E(G)}={1,2,…,|E|},則稱G為強協(xié)調(diào)圖，f為G的強協(xié)調(diào)標號。

定義3[2]設(shè)G=是平面圖，u,v是圖中任意兩個不相鄰的頂點，若G+uv是非平面圖，則稱G=為極大平面圖。

定義4[2]在圖G的每個頂點上都粘接1條邊所得的圖稱為G的冠，記為I(G)。

2 主要結(jié)論

引理1圖G可嵌入球面S當且僅當G可嵌入平面π。

引理2設(shè)G是p(p≥3)階簡單平面圖，則G是極大平面圖當且僅當|E(G)|=3p-6。

證明根據(jù)圖的冠的定義及定理1可知，結(jié)論成立。

證明顯然|E(Gp)|=3p-6，|V(Gp)|=p

建立映射f:V(Gp)→{0,1,2,…,3p-6}

f(v1)=0,f(v2)=2p-4,f(v3)=3p-6；

f(ui)=i,i=1,2,…,p-3

下證f是Gp的優(yōu)美標號。由上述標號可知f滿足：

1)顯然，對任意的u,v∈V，若u≠v，則f(u)≠f(v)；

2)顯然，max{f(v)|f∈V}=|E|=3p-6；

3)令g(e)=|f(u)-f(v)|，e=uv,下證{f(e)|e∈E}={1,2,…,|E|}。由標號f有：

{f(v1ui)=i,i=1,2,…,p-3}={1，2，…，p-3}；

f(v2v3)=p-2；

{f(v2ui)=p-2+(p-2-i)=2p-4-i,i=1,2,…,p-3}={p-1,p-2,…,2p-5}；

f(v1v2)=2p-4；

{f(v3ui)=2p-4+(p-2-i)=3p-6-i,i=1,2,…,p-3}={2p-3,2p-2,…,3p-5}；

f(v1v3)=3p-6=|E|

故{g(e)|e∈E}={1,2,…,|E|}。綜上可知f是Gp的優(yōu)美標號，所以Gp是優(yōu)美圖。

證明由|V(Gp)|=p，|E(Gp)|=3p-6可知，I(Gp)中有2p個頂點，4p-6條邊。設(shè)I(Gp)中與vi相鄰的懸掛點為wi，與uj相鄰的懸掛點為tj，i=1，2，3；j=1,2,…,p-3。建立映射f：V(I(Gp))→{0，1，2，…，4p-6}如下：

f(v1)=0，f(v2)=2p-4,f(v3)=4p-6；

f(w1)=2p-3，f(w2)=p-2，f(w3)=2p-5；

f(ui)=i,i=1,2,…,p-3；

f(ti)=2p+1+2(i-1),i=1,2,…,p-3

同樣可驗證f是I(Gp)的一個優(yōu)美標號，從而I(Gp)是優(yōu)美圖。

證明建立映射f:V(Gp)→{0,1,2,…,3p-6}如下：

f(v1)=0，f(v2)=1,f(v3)=2；

f(ui)=3i+1,i=1,2,…,p-3

下證f是Gp的強協(xié)調(diào)標號。

1) 顯然f是單射;

2)下證對?uv∈E(G),令f(uv)=f(u)+f(v)，有{f(uv)∣uv∈E(G)}={1,2,…,|E|}。由上述標號可知f有：

f(v1v2)=1，f(v1v3)=2，f(v2v3)=3；

{f(v1ui)=3i+1,i=1,2,…,p-3}={4，7，…，3p-8}；

{f(v2ui)=3i+2,i=1,2,…,p-3}={5，8，…，3p-7}；

{f(v3ui)=3i+3,i=1,2,…,p-3}={6，9，…，3p-6}

因此有{f(uv)∣uv∈E(G)}={1,2,…,|E|}。綜上可知f是Gp的強協(xié)調(diào)標號，所以Gp是強協(xié)調(diào)圖。

證明建立f:V(I(GP))→{0,1,2,…,4p-6}映射如下：

f(v1)=0，f(v2)=1,f(v3)=2；

f(w1)=3p-4，f(w2)=3p-6，f(w3)=4p-8；

f(ui)=3i+1,i=1,2,…,p-3；

f(ti)=5+4(p-3-i),i=1,2,…,p-3

同樣可驗證f是I(Gp)的一個強協(xié)調(diào)標號，從而I(Gp)是強協(xié)調(diào)圖。