图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