圖Pa，b的k-優美性

嚴謙泰，姚艷紅

(安陽師范學院數學與統計學院，河南 安陽 455000)

?

圖Pa，b的k-優美性

嚴謙泰，姚艷紅

(安陽師范學院數學與統計學院，河南 安陽 455000)

[摘要]利用函數構造的方法得到了圖P2和圖P2的一個k-優美標號，從而證明了圖P2和圖P2的k-優美性.

[關鍵詞]優美圖；k-優美圖；頂點標號

1預備知識

定義3設u，v是兩個固定頂點. 用b條內部互不相交且長度皆為a的道路連接u，v所得的圖稱為圖Pa，b.

本文研究了圖Pa，b的k-優美性.文中未加說明的術語和記號參見文獻[1].

2主要結果

定理1圖P2r+1，2m+1是k-優美圖.

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

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

當j為奇數且0

當j為偶數，i為奇數且0

當j為偶數，i為偶數且0

下面證明f是P2r+1，2m+1的一個k-優美標號.

首先證明P2r+1，2m+1各頂點標號不同.

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

即對任意的u，v∈V，若u≠v，則f(u)≠f(v).從而P2r+1，2m+1的頂點標號各不相同，且有

其次證明各邊標號不同.記：

故P2r+1，2m+1所有邊的標號各不相同.

由k-優美標號的定義知，f是P2r+1，2m+1的一個k-優美標號.

定理2P2r，b圖是k-優美圖.

0

0

下面證明f是P2r，b的一個k-優美標號.

，

，

.

，

，

.

顯然第i條道路奇數列頂點的標號單調遞增，第i條道路偶數列頂點的標號單調遞減，且

，

，

，

從而當

b+12

時，第i條道路上第2到第2r-1條邊的標號單調遞減；當

≤i≤b時，第i條道路上第2到第2r-1條邊的標號單調遞增.且當b為偶數時，

當b為奇數時，

故P2r，b的邊和標號一一對應.

綜上可知，f是P2r，b的k-優美標號，從而P2r，b是k-優美圖.

[參考文獻]

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

[3]吳躍生.非連通圖2C4m∪C8m-1∪G的優美標號[J].東北師大學報(自然科學版)，2015，47(3):60-63.

[4]楊元生，容青，徐喜榮.一類優美圖[J].數學研究與評論，2004，24:520-524.

[5]嚴謙泰.圖P2r，2m的優美標號[J].系統科學與數學，2006，26(5):513-517

(責任編輯：李亞軍)

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

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

[文獻標志碼]A

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

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

[收稿日期]2014-08-21

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

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