徐美进，刘春峰，高 洋

一类图的优美标号与序列标号

徐美进1，刘春峰2，高 洋3

（1.辽宁工业大学 理学院，辽宁 锦州 121001；2.中国人民政治协商会议辽宁省锦州市委员会，辽宁 锦州 121001；3.沈阳城市建设学院 基础教研部，辽宁 沈阳 110167）

研究了图的标号问题，通过图的运算以及关联关系构造出一个新的图类P()()，利用函数对应关系给出了该类图P()()对应的优美标号和序列标号，并分多种情况加以讨论说明，从而证明了该类图是优美图和序列图。

优美图；序列图；顶点标号

1 预备知识

图P(s)()如图1所示。

图1 图Pm(s)(n)

2 定理及证明

证明 分两种情况证明定理1。

情况1≡0(mod2)

定义图P(s)()的顶点标号如式(1)所示。

下面验证是图P(s)()的优美标号。

(1)图P(s)()中不同的点，其标号不同。设

(2)最大最小为

(3)图P(s)()中若边不同，则其标号不同。

由(1)式，有

假设

由上述可知是图P(s)()的一个优美标号，图P(s)()是优美图。

情况2≡1(mod2)

定义图P(s)()的顶点标号如式(2)所示。

在情况2中，可与情况1同样验证是图P(s)()的一个优美标号，图P(s)()是优美图。

定理1证毕。

图2和图3给出了图3(2)(4)和图4(2)(3)的优美标号。

图2 图P3(2)(4)的优美标号

图3 图P4(2)(3)的优美标号

定理2 若(＞1)、和是正整数，则图P(s)()是序列图。

证明 分两种情况证明定理2。

情况1≡0(mod2)

(1)图P(s)()中若点不同，其则标号亦不相同。设

(3)图P(s)()中若边不同，其则标号亦不相同。

根据式(3)，有

假设

于是，有

由上述可知是图P(s)()的一个序列标号，图P(s)()是序列图。

情况2≡1(mod2)

在情况2中，可与情况1同样验证是图P(s)()的一个序列标号，图P(s)()是序列图。

定理2证毕。

图4和图5给出了图4(1)(4)和2(3)(3)图的序列标号。

图4 图P4(1)(4)的序列标号

图5 图P2(3)(3)的序列标号

由定理1及定理2，有如下推论。……