圖Pa，b的k-優(yōu)美性

嚴(yán)謙泰，姚艷紅

(安陽(yáng)師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 安陽(yáng) 455000)

?

圖Pa，b的k-優(yōu)美性

嚴(yán)謙泰，姚艷紅

(安陽(yáng)師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 安陽(yáng) 455000)

[摘要]利用函數(shù)構(gòu)造的方法得到了圖P2和圖P2的一個(gè)k-優(yōu)美標(biāo)號(hào)，從而證明了圖P2和圖P2的k-優(yōu)美性.

[關(guān)鍵詞]優(yōu)美圖；k-優(yōu)美圖；頂點(diǎn)標(biāo)號(hào)

1預(yù)備知識(shí)

定義3設(shè)u，v是兩個(gè)固定頂點(diǎn). 用b條內(nèi)部互不相交且長(zhǎng)度皆為a的道路連接u，v所得的圖稱為圖Pa，b.

本文研究了圖Pa，b的k-優(yōu)美性.文中未加說(shuō)明的術(shù)語(yǔ)和記號(hào)參見(jiàn)文獻(xiàn)[1].

2主要結(jié)果

定理1圖P2r+1，2m+1是k-優(yōu)美圖.

f(u)=k+(2r+1)(2m+1)-1；

f(v)=((2r+1)(2m-1)-1)/2.

當(dāng)j為奇數(shù)且0

當(dāng)j為偶數(shù)，i為奇數(shù)且0

當(dāng)j為偶數(shù)，i為偶數(shù)且0

下面證明f是P2r+1，2m+1的一個(gè)k-優(yōu)美標(biāo)號(hào).

首先證明P2r+1，2m+1各頂點(diǎn)標(biāo)號(hào)不同.

顯然每個(gè)f(Vj)中的序列從上到下單調(diào)遞增且f(V1)

即對(duì)任意的u，v∈V，若u≠v，則f(u)≠f(v).從而P2r+1，2m+1的頂點(diǎn)標(biāo)號(hào)各不相同，且有

其次證明各邊標(biāo)號(hào)不同.記：

故P2r+1，2m+1所有邊的標(biāo)號(hào)各不相同.

由k-優(yōu)美標(biāo)號(hào)的定義知，f是P2r+1，2m+1的一個(gè)k-優(yōu)美標(biāo)號(hào).

定理2P2r，b圖是k-優(yōu)美圖.

0

0

下面證明f是P2r，b的一個(gè)k-優(yōu)美標(biāo)號(hào).

，

，

.

，

，

.

顯然第i條道路奇數(shù)列頂點(diǎn)的標(biāo)號(hào)單調(diào)遞增，第i條道路偶數(shù)列頂點(diǎn)的標(biāo)號(hào)單調(diào)遞減，且

，

，

，

從而當(dāng)

b+12

時(shí)，第i條道路上第2到第2r-1條邊的標(biāo)號(hào)單調(diào)遞減；當(dāng)

≤i≤b時(shí)，第i條道路上第2到第2r-1條邊的標(biāo)號(hào)單調(diào)遞增.且當(dāng)b為偶數(shù)時(shí)，

當(dāng)b為奇數(shù)時(shí)，

故P2r，b的邊和標(biāo)號(hào)一一對(duì)應(yīng).

綜上可知，f是P2r，b的k-優(yōu)美標(biāo)號(hào)，從而P2r，b是k-優(yōu)美圖.

[參考文獻(xiàn)]

[1]SHEPPARD D A. The factorial representation of majorbalanced labeled graphs[J].Discrete Math，1976，15:379-388.

[3]吳躍生.非連通圖2C4m∪C8m-1∪G的優(yōu)美標(biāo)號(hào)[J].東北師大學(xué)報(bào)(自然科學(xué)版)，2015，47(3):60-63.

[4]楊元生，容青，徐喜榮.一類優(yōu)美圖[J].數(shù)學(xué)研究與評(píng)論，2004，24:520-524.

[5]嚴(yán)謙泰.圖P2r，2m的優(yōu)美標(biāo)號(hào)[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2006，26(5):513-517

(責(zé)任編輯：李亞軍)

k-gracefulness of graphPa，b

YAN Qian-tai，YAO Yan-hong

(School of Mathematics and Statistics，Anyang Normal University，Anyang 455000，China)

Abstract:A k-graceful labeling for all the P2 and P2 are given by function constructing. So the k-gracefulness of P2 and P2 are proved.

Keywords:graceful graph；k-graceful graph；vertex labeling

[中圖分類號(hào)]O 157.5[學(xué)科代碼]110·7470

[文獻(xiàn)標(biāo)志碼]A

[作者簡(jiǎn)介]嚴(yán)謙泰(1964—)，男，教授，主要從事圖論及其應(yīng)用研究；通訊作者：姚艷紅，碩士，講師，主要從事圖論及其應(yīng)用研究.

[基金項(xiàng)目]河南省自然科學(xué)基金資助項(xiàng)目(0511013800)；河南省教育廳自然科學(xué)基金資助項(xiàng)目(12A110003).

[收稿日期]2014-08-21

[文章編號(hào)]1000-1832(2016)01-0008-06

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