5類(lèi)圖的優(yōu)美性

唐保祥, 任 韓

(1.天水師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 天水 741001; 2.華東師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 上海 200062)

1 引言與預(yù)備知識(shí)

優(yōu)美圖在晶體結(jié)構(gòu)中的原子位置測(cè)定、物流運(yùn)輸、編碼設(shè)計(jì)、通訊網(wǎng)絡(luò)、X射線密碼技術(shù)、天文學(xué)、導(dǎo)彈控制、雷達(dá)和數(shù)據(jù)庫(kù)管理等領(lǐng)域應(yīng)用廣泛[1-2].但目前對(duì)一般圖的優(yōu)美性研究尚無(wú)系統(tǒng)性理論.研究表明, 判定任意一個(gè)圖是否為優(yōu)美圖是一個(gè)NP難問(wèn)題.目前, 對(duì)圖優(yōu)美性的證明一般仍用構(gòu)造性方法[3-17].

最省刻度尺問(wèn)題為： 設(shè)m,n為正整數(shù), 在長(zhǎng)為n(任意一個(gè)確定的值)厘米的無(wú)刻度尺上添加m個(gè)刻度(包括直尺兩端的刻度), 使其可以度量1～n內(nèi)任何整厘米長(zhǎng)度的尺寸, 求m的值至少是多少.該問(wèn)題的一般情形目前尚未解決[17].

定義1[1]設(shè)圖G=(V,E), 若存在單射θ:V(G)→{0,1,2,…,|E(G)|}, 使得?e=uv∈E(G), 由θ′(e)=|θ(u)-θ(v)|可導(dǎo)出雙射θ′:E(G)→{1,2,…,|E(G)|}, 則稱圖G是優(yōu)美圖,θ稱為圖G的一個(gè)優(yōu)美標(biāo)號(hào),θ′稱為由θ導(dǎo)出的邊標(biāo)號(hào).

定義2[12-13]給定邊數(shù)的優(yōu)美圖中頂點(diǎn)數(shù)最少的優(yōu)美圖稱為極小優(yōu)美圖.

把完全二部圖K2,n的頂點(diǎn)w與全圖K3的頂點(diǎn)u0連接一條邊, 再把K2,n的頂點(diǎn)v0與K3的頂點(diǎn)u0,u1,u2分別連接一條邊得到的圖記作K2,n-1-3-K3, 如圖1所示.把完全二部圖K2,n的頂點(diǎn)w與全圖K3的頂點(diǎn)u0,u1分別連接一條邊, 再把K2,n的頂點(diǎn)v0與K3的頂點(diǎn)u0,u1分別連接一條邊得到的圖記作K2,n-2-2-K3, 如圖2所示.

圖1 圖K2,n-1-3-K3Fig.1 Graph K2,n-1-3-K3

圖2 圖K2,n-2-2-K3Fig.2 Graph K2,n-2-2-K3

把完全二部圖K2,n的頂點(diǎn)w與全圖K3的頂點(diǎn)u0連接一條邊, 再把K2,n的頂點(diǎn)v0與K3的頂點(diǎn)u0,u1分別連接一條邊得到的圖記作K2,n-1-2-K3, 如圖3所示.把完全二部圖K1,n的頂點(diǎn)v0與K3的頂點(diǎn)u0,u1分別連接一條邊得到的圖記作K1,n-2-K3, 如圖4所示.把完全二部圖K1,n的頂點(diǎn)v0與有3個(gè)頂點(diǎn)的路P3的頂點(diǎn)u1,u0,u2分別連接一條邊得到的圖記作K1,n-3-P3, 如圖5所示.

圖3 圖K2,n-1-2-K3Fig.3 Graph K2,n-1-2-K3

圖4 圖K1,n-2-K3Fig.4 Graph K1,n-2-K3

圖5 圖K1,n-3-P3Fig.5 Graph K1,n-3-P3

n個(gè)整數(shù)單位長(zhǎng)度的直尺, 最少添加m個(gè)刻度(這m個(gè)刻度包括尺子的兩個(gè)端點(diǎn)), 使得能度量1～n內(nèi)任何整數(shù)單位長(zhǎng)度的尺寸, 這樣的直尺度量方式, 對(duì)應(yīng)一個(gè)圖: 有m個(gè)頂點(diǎn)、n條邊的圖, 任意一對(duì)頂點(diǎn)的兩個(gè)數(shù)值較大數(shù)與較小數(shù)之差恰好是1,2,…,n.此時(shí)該圖形為一個(gè)極小優(yōu)美圖.

本文證明5類(lèi)結(jié)構(gòu)相似但不同構(gòu)的圖是優(yōu)美圖.當(dāng)1≤n≤5時(shí), 圖K2,n-1-3-K3,K2,n-2-2-K3,K2,n-1-2-K3和K1,n-3-P3都是極小優(yōu)美圖.因此, 每個(gè)n值對(duì)應(yīng)圖的頂點(diǎn)標(biāo)號(hào), 均可給出對(duì)應(yīng)尺長(zhǎng)(圖的邊數(shù))的最省刻度.圖K2,n-1-3-K3,K2,n-1-2-K3和K1,n-3-P3中n=1～5, 得到15組對(duì)應(yīng)尺長(zhǎng)最省刻度的數(shù)值.

2 主要結(jié)果

圖6 圖K2,n-1-3-K3的優(yōu)美標(biāo)號(hào)Fig.6 Graceful labeling of graph K2,n-1-3-K3

定理1?n∈+, 圖K2,n-1-3-K3是優(yōu)美圖.

證明: 設(shè)圖K2,n-1-3-K3的頂點(diǎn)集合為{u0,u1,u2,w,vi|i=0,1,2,…,n}, 由圖K2,n-1-3-K3的定義知

|E(K2,n-1-3-K3)|=5n+7,

|V(K2,n-1-3-K3)|=n+5.

定義圖K2,n-1-3-K3頂點(diǎn)的標(biāo)號(hào)θ1如下:

θ1(u0)=0,θ1(u1)=n+1,

θ1(u2)=2n+3,θ1(w)=3n+5;

θ1(vi)=4n+7+i,i=0,1,2,…,n.

圖K2,n-1-3-K3的標(biāo)號(hào)θ1如圖6所示.根據(jù)標(biāo)號(hào)θ1的定義, 圖K2,n-1-3-K3的集合為{u0,u1,u2,w,vi|i=0,1,2,…,n}, 定義的標(biāo)號(hào)集合為{0,n+1,2n+3,4n+7+i|i=0,1,2,…,n}.所以映射θ1:V(K2,n-1-3-K3)→{0,1,2,…,5n+7}是單射.

映射θ1導(dǎo)出的邊標(biāo)號(hào)如下:

定理2?n∈+, 圖K2,n-2-2-K3是優(yōu)美圖.

證明: 設(shè)圖K2,n-2-2-K3的頂點(diǎn)集合為{u0,u1,u2,w,vi|i=0,1,2,…,n}, 由圖K2,n-2-2-K3的定義知,

|E(K2,n-2-2-K3)|=5n+7,

|V(K2,n-2-2-K3)|=n+5.

定義圖K2,n-1-2-K3頂點(diǎn)的標(biāo)號(hào)θ3如下:

θ2(u0)=0,θ2(u1)=n+1,θ2(u2)=2n+3,θ2(w)=3n+5;

θ2(vi)=4n+7+i,i=0,1,2,…,n.

圖K2,n-2-2-K3的標(biāo)號(hào)θ2如圖7所示.

類(lèi)似定理1的證明易知,θ2是圖K2,n-2-2-K3的一個(gè)優(yōu)美標(biāo)號(hào), 因此圖K2,n-2-2-K3是優(yōu)美圖.

定理3?n∈+, 圖K2,n-1-2-K3是優(yōu)美圖.

證明: 設(shè)圖K2,n-1-2-K3的頂點(diǎn)集合為{u0,u1,u2,w,vi|i=0,1,2,…,n}, 由圖K2,n-1-2-K3的定義知

|E(K2,n-1-2-K3)|=5n+6,

|V(K2,n-1-2-K3)|=n+5.

定義圖K2,n-1-2-K3頂點(diǎn)的標(biāo)號(hào)θ3如下:

θ3(u0)=0,θ3(u1)=n+1,θ3(u2)=2n+3,θ3(w)=3n+4;

θ3(vi)=4n+6+i,i=0,1,2,…,n.

圖K2,n-1-2-K3的標(biāo)號(hào)θ3如圖8所示.

圖7 圖K2,n-2-2-K3的優(yōu)美標(biāo)號(hào)Fig.7 Graceful labeling of graph K2,n-2-2-K3

圖8 圖K2,n-1-2-K3的優(yōu)美標(biāo)號(hào)Fig.8 Graceful labeling of graph K2,n-1-2-K3

類(lèi)似定理1的證明易知,θ3是圖K2,n-1-2-K3的一個(gè)優(yōu)美標(biāo)號(hào), 所以圖K2,n-1-2-K3是優(yōu)美圖.

定理4?n∈+, 圖K1,n-2-K3是優(yōu)美圖.

證明: 設(shè)圖K1,n-2-K3的頂點(diǎn)集合為{u0,u1,u2,vi|i=0,1,2,…,n}, 由圖K1,n-2-K3的定義知,

|E(K1,n-2-K3)|=4n+5,

|V(K1,n-2-K3)|=n+4.

定義圖K1,n-2-K3頂點(diǎn)的標(biāo)號(hào)θ4如下:

θ4(u0)=0,θ4(u1)=n+1,θ4(u2)=2n+3;

θ4(vi)=4n+5+i,i=0,1,2,…,n.

圖K1,n-2-K3的標(biāo)號(hào)θ4如圖9所示.

類(lèi)似定理1的證明易知,θ4是圖K1,n-2-K3的一個(gè)優(yōu)美標(biāo)號(hào), 所以圖K1,n-2-K3是優(yōu)美圖.

定理5?n∈+, 圖K1,n-3-P3是優(yōu)美圖.

證明: 設(shè)圖K1,n-3-P3的頂點(diǎn)集合為{u0,u1,u2,vi|i=0,1,2,…,n}, 由圖K1,n-3-P3的定義知,

|E(K1,n-3-P3)|=4n+5,

|V(K1,n-2-K3)|=n+4.

定義圖K1,n-3-P3頂點(diǎn)的標(biāo)號(hào)θ5如下:

θ5(u0)=0,θ5(u1)=n+1,θ5(u2)=2n+3;

θ5(vi)=3n+5+i,i=0,1,2,…,n.

圖K1,n-3-P3的標(biāo)號(hào)θ5如圖10所示.

圖9 圖K1,n-2-K3的優(yōu)美標(biāo)號(hào)Fig.9 Graceful labeling of graph K1,n-2-K3

圖10 圖K1,n-3-P3的優(yōu)美標(biāo)號(hào)Fig.10 Graceful labeling of graph K1,n-3-P3

類(lèi)似定理1的證明易知,θ5是圖K1,n-3-P3的一個(gè)優(yōu)美標(biāo)號(hào), 所以圖K1,n-3-P3是優(yōu)美圖.

3 應(yīng) 用

文獻(xiàn)[12]已經(jīng)證明: 邊數(shù)為m的極小優(yōu)美圖G的頂點(diǎn)數(shù)為f(m), 則

其中[x]表示大于等于x的最小整數(shù).

根據(jù)上述結(jié)論, 當(dāng)1≤n≤5時(shí), 圖K2,n-1-3-K3,K2,n-2-2-K3,K2,n-1-2-K3和K1,n-3-P3都是極小優(yōu)美圖.因此, 每個(gè)n值對(duì)應(yīng)圖的頂點(diǎn)標(biāo)號(hào), 都給出了對(duì)應(yīng)尺長(zhǎng)(圖的邊數(shù))的最省刻度.圖K2,n-1-3-K3,K2,n-1-2-K3和K1,n-3-P3中n=1～5, 對(duì)應(yīng)尺長(zhǎng)的最省刻度分別列于表1～表3.

表1 K2,n-1-3-K3的邊數(shù)、頂點(diǎn)數(shù)及對(duì)應(yīng)的最省直尺刻度值

表2 K2,n-1-2-K3的邊數(shù)、頂點(diǎn)數(shù)及對(duì)應(yīng)的最省直尺刻度值

表3 K2,n-3-P3的邊數(shù)、頂點(diǎn)數(shù)及對(duì)應(yīng)的最省直尺刻度值