时间：2022-08-09 10:47:03
摘要：定义了图Pn3。给出了。图Pn3 的优美标号，从而证明了图Pn3是优美图，并且是平衡二分图，也是交错图。
关键词：优美图；优美标号；图Pn3;平衡二分图；交错图
中图分类号：TP311文献标识码：A 文章编号：1009-3044(2007)06-11661-04
1 引言
优美图是图论中比较活跃的一个分支。优美图的研究由Ringel1963年的一个猜想引起的。本文研究一类特殊图Pn3的优美性。
定义2 在含有n个顶点的路Pn上，当且仅当两点的距离为3时增加一条边所得到的图叫Pn3。
定义3 设f(u)为优美图G的一个优美标号。若存在整数k,对任意（u,v）∈E(G)有f(u)≤k,f(v)>k，则称这种优美标号为平衡标号。称满足f(u0)=k的顶点为该图的平衡二分点。
定义4 图G有平衡标号f.设u0为图G的平衡二分点，则一定有一个二划分（V1,V2），其中V1={v:f(v)≤k,v∈V(G)},V2={v:f(v)> k,v∈V(G)}即具有平衡标号的优美图一定为二分图，具有平衡二分划的优美图又叫平衡二分图。
定义5 G是一个有n个顶点的优美二分图，其优美标号为f，V可分成2个集合X，和Y如果有max{f(X)}≤min{f(Y)}，则称G为交错图，称f是G的交错标号。
为叙述方便，本文所讨论的图都为无向简单图。既v表示点也表示点的标号。点v2p称为偶点，点v2p+1称为奇点，其余术语均来自[1]
2 主要结果
定理1 对任意自然数n,图Pn3都是优美图。
定理2 对任意自然数n,图Pn3都是平衡二分图
定理3 对任意自然数n,图Pn3都是交错图。
3 定理的证明
我们分以下若干定理证明之
定理3.1.1 当n=4,5时,Pn3都是优美图
定理3.1.2当n=4,5时Pn3都是平衡二分图
定理3.1.3当n=4,5时，Pn3都是交错图。
证明：给出优美标号如图1所示。
由定义易知命题成立。
定理3.2.1对任意自然数K，当n=6k图Pn3都是优美图。(|E|=12k-4)
图1
定理3.2.2对任意自然数K，当n=6k图Pn3都是平衡二分图。
定理3.2.3对任意自然数K，当n=6k图Pn3都是交错图。
我们先给出顶点标号递推算法1：
1)设P=v0，v1，v2，v3…vn-1, 图Pn3各顶点的标号如果已给出，依此为v0,v1,v2…vn-1;
2)当n`=6(K+1)时，图Pn3各点标号如下：
3)当即时，图Pn3各点标号如图3
按照以上的递推算法1，对任意自然数k，当n=6k时图Pn3具有如下性质，
图2
性质3.2.1图Pn3中的奇点标号从大到小排列。
证明 当k=1时，由图3命题成立；
假设k=p时，即n=6p时命题成立；
当k=p+1即n`=6(p+1)时，由算法及假设有v1`=v1+12＞v3+12=v3`>…>v6p-1`由b)有, v6p+1`= v6p-1`-3< v6p-1`, v6p+3`= v6p-1`-4
性质3.2.2图Pn3中的奇点标号都比所有偶点的标号大。
证明当k=1时，由图3命题成立。
假设当k=p时，即n=6p时命题成立即有v6p-1＞v2s(2s≤6p-2,s=0,1,2,…)
当k=p+1时即n`=6(p+1)时，由算法1中b)有v6p+5`＞v6p+4` ＞v6p+2`＞v6p`又由假设及性质3、2、1知，当k=p+1时，命题成立。
性质3.2.3图Pn3中的偶点标号从小到大排列。
证明当k=1即n=6,显然命题成立。
假设k=p时，即n=6p时命题成立 即v0＜v2＜v4＜…＜v6p-2。
性质3.2.4图Pn3中的所有的顶点的标号各不相同，即f:V(Pn3){0,1,2,…12k-4}是单射。
证明由算法1及性质3.2.1，3.2.2，3.2.3可知，f是单射。
性质3.2.5 图Pn3中的所有的边的标号为{1，2，…12k-4}.
证明当k=1时，即n=6时命题显然成立
定理3.2.1的证明 由性质3.2.4，3.2.5，对任意自然数k,当n=6k时，图Pn3存在一个优美标号。由定义1，图Pn3优美图
定理3.2.2的证明 令V1={d(u,v0)偶数―u∈G},V2={ d(u,v0)奇数―u∈G}
存在k=f(v6p-2)由性质3.2.2，3.2,3知图Pn3都是平衡二分图。
定理3.2.3的证明 由性质3.2.2知，max{f(V1)}＜min{f(V2)}即图Pn3都是交错图
定理3.3.1对任意自然数K，当n=6k+1时，图Pn3都是优美图。(|E|=12k-2)
定理3.3.2对任意自然数K，当n=6k+1时，图Pn3都是平衡二分图。
定理3.3.3对任意自然数K，当n=6k+1时，图Pn3都是交错图。
先给出各顶点标号递推算法2：
1)设P=v0v1v2v3…vn-1, 图Pn3各顶点的标号如果已给出，依此为v0,v1,v2…vn-1;
2)当n`=6(K+1)+1时，图Pn3各点标号如下：
3)当k=1即n=7时，图Pn3各点标号如图3。
图3
按照以上的递推算法1，对任意自然数k，当n=6k+1时图Pn3具有如下性质，
性质3.3.1图Pn3中的奇点标号从大到小排列。
证明 当k=1时，由图3命题成立；
假设k=p时，即n=6p+1时命题成立；
性质3.3.2图Pn3中的奇点标号都比所有偶点的标号大。
证明当k=1时，由图3命题成立
假设当k=p时，即n=6p时命题成立即有v6p-1＞v2s(2s≤6p,s=0,1,2,…)
当k=p+1时即n`=6(p+1)时，由算法2中b)有v6p+5`＞v6p+6`＞v6p+4` ＞v6p+2`＞v6p`又由假设及性质3.2.1知，当k=p+1时，命题成立。
性质3.3.3图Pn3中的偶点标号从小到大排列。
证明当k=1即n=7,显然命题成立
假设k=p时，即n=6p+1时命题成立 即v0＜v2＜v4＜…＜v6p
性质3.3.4图Pn3中的所有的顶点的标号各不相同，即f:V(Pn3){0,1,2,…12k-2}是单射
证明由算法1及性质3.2.1，3.2.2，3.2.3可知，f是单射。
性质3.3.5 图Pn3中的所有的边的标号为{1，2，…12k-2}.
证明当k=1时，即n=7时命题显然成立
定理3.3.2的证明 令V1={d(u,v0)偶数―u∈G},V2={ d(u,v0)奇数―u∈G}
存在k=f(v6p-2)由性质3.2.2，3.2,3知图Pn3都是平衡二分图。.
定理3.3.3的证明 由性质3.2.2知，max{f(V1)}＜min{f(V2)}即图Pn3都是交错图
定理3.4.1对任意自然数K，当n=6k+2时，图Pn3都是优美图。(|E|=12k)
定理3.4.2对任意自然数K，当n=6k+2时，图Pn3都是平衡二分图
定理3.4.3对任意自然数K，当n=6k+2时，图Pn3都是交错图
我们先给出顶点标号递推算法1：
1)设P=v0v1v2v3…vn-1, 图Pn3各顶点的标号如果已给出，依此为v0,v1,v2…vn-1;
2)当n`=6(K+1)时，图Pn3各点标号如下：
3)当即时，图Pn3各点标号如图4。
图4
按照以上的递推算法1，对任意自然数k，当n=6k+2时图Pn3具有如下性质，
性质3.4.1图Pn3中的奇点标号从大到小排列。
证明 当k=1时，n=8由图3命题成立；
假设k=p时，即n=6p+2时命题成立；
性质3.4.2图Pn3中的奇点标号都比所有偶点的标号大。
证明当k=1时，由图4命题成立。
假设当k=p时，即n=6p+2时命题成立即有v6p+1＞v2s(2s≤6p.s,t=0,1,2,…)。
性质3.4.3图Pn3中的偶点标号从小到大排列。
证明当k=1即n=8,显然命题成立。
性质3.4.4图Pn3中的所有的顶点的标号各不相同＞，即f:V(Pn3){0,1,2,…12k}是单射。
证明由算法/及性质3.4.1，3.4.2，3.4.3可知，f是单射。
性质3.4.5 图Pn3中的所有的边的标号为{1，2，…12k}。
证明当k=1时，即n=8时命题显然成立。
定理3.4.1的证明 由性质3.4.4，3.4.5，对任意自然数k,当n=6k+2时， 图Pn3存在一个优美标号。由定义1，图Pn3优美图
定理3.4.2的证明 令V1={d(u,v0)偶数―u∈G},V2={ d(u,v0)奇数―u∈G}
存在k=f(v6p)由性质3.4.2，3.4,3知图Pn3都是平衡二分图。
定理3.4.3的证明 由性质3.4.2知，max{f(V1)}＜min{f(V2)}即图Pn3都是交错图。
定理3.5.1对任意自然数K，当n=6k+3时，图Pn3都是优美图。(|E|=12k+2)
定理3.5.2对任意自然数K，当n=6k+3时，图Pn3都是平衡二分图。
定理3.5.3对任意自然数K，当n=6k+3时，图Pn3都是交错图。
先给出各顶点标号递推算法2：
1)设P=v0v1v2v3…vn-1, 图Pn3各顶点的标号如果已给出，依此为v0v1v2v3…vn-1;
2)当n`=6(K+1)+3时，图Pn3各点标号如下：
3)当k=1即n=9时，图Pn3各点标号如图5。
图5
性质3.5.1图Pn3中的奇点标号从大到小排列。
证明 当k=1时，n=9由图3命题成立；
假设k=p时，即n=6p+3时命题成立；
性质3.5.2图Pn3中的奇点标号都比所有偶点的标号大。
证明当k=1时，由图6命题成立。
假设当k=p时，即n=6p+3时命题成立即有v6p+1＞v2s(2s≤6p.s,t=0,1,2,…)。
性质3.5.3图Pn3中的偶点标号从小到大排列。
证明当k=1即n=9,显然命题成立。
假设k=p时，即n=6p+3时命题成立，即v0＜v2＜v4＜…＜v6p+2。
性质3.5.4图Pn3中的所有的顶点的标号各不相同＞，即f:V(Pn3){0,1,2,…12k+2}是单射。
证明由算法及性质35.1，3.5.2，3.5.3可知，f是单射。
性质3.5.5 图Pn3中的所有的边的标号为{1，2，…12k+2}.
证明当k=1时，即n=9时命题显然成立。
定理3.5.1的证明 由性质3.4.4，3.4.5，对任意自然数k,当n=6k+3时，图Pn3存在一个优美标号。由定义1，图Pn3优美图
定理3.5.2的证明 令V1={d(u,v0)偶数―u∈G},V2={ d(u,v0)奇数―u∈G}
存在k=f(v6p-2)由性质3.5.2，3.5.3知图Pn3都是平衡二分图。
定理3.5.3的证明 由性质3.5.2知，max{f(V1)}＜min{f(V2)}即图Pn3都是交错图
定理3.6.1对任意自然数K，当n=6k+4时，图Pn3都是优美图。(|E|=12k+4)
定理3.6.2对任意自然数K，当n=6k+4时，图Pn3都是平衡二分图
定理3.6.3对任意自然数K，当n=6k+4时，图Pn3都是交错图
先给出各顶点标号递推算法2：
1）设P=v0v1v2v3…vn-1, 图Pn3各顶点的标号如果已给出，依此为v0,v1,v2…vn-1;
2)当n`=6(K+1)+4时，图Pn3各点标号如下：
a) 图Pn`3中的点v0`,v1`,v2`…v6k`有v2s`=v2s,v2t+1`=v2t+1+12(2s,≤6k+2,s,t,=0,1,2,…)；
b)图Pn`3中的其它各点如下标号：v6k+4`= v6k+3`-11，v6k+5`= v6k+3`-3, v6k+6`= v6k+3`-9，v6k+7`=v6k+3`-4,v6k+7`= v6k+3`-6,v6k+9`=v6k+3`-5。
3)当k=1即n=10时，图Pn3各点标号如图：
图6
性质3.6.1图Pn3中的奇点标号从大到小排列。
证明 当k=1时，n=10由图7命题成立；
假设k=p时，即n=6p+4时命题成立；
当k=p+1即n`=6(p+1)+4时，由算法及假设有v1`=v1+12＞v3+12=v3`>…>v6p+3`b)有v6p+3`＞v6p+5`>v6p+7`＞v6p+9` ,由数学归纳法，命题成立。
性质3.6.2图Pn3中的奇点标号都比所有偶点的标号大。
证明当k=1时，由图7命题成立
假设当k=p时，即n=6p+4时命题成立即有v6p+3＞v2s(2s≤6p.s,t=0,1,2,…)
性质3.6.3图Pn3中的偶点标号从小到大排列。
证明当k=1即n=10,显然命题成立
假设k=p时，即n=6p+4时命题成立 即v0＜v2＜v4＜…＜v6p+2
性质3.6.4图Pn3中的所有的顶点的标号各不相同＞，即f:V(Pn3){0,1,2,…12k+2}是单射。
证明由算法1及性质3.6.1，3.6.2，3.6.3可知，f是单射。
性质3.6.5图Pn3中的所有的边的标号为{1，2，…12k+4}.
证明当k=1时，即n=10时命题显然成立
定理3.6.1的证明 由性质3.4.4，3.4.5，对任意自然数k,当n=6k时，图Pn3存在一个优美标号。由定义1，图Pn3优美图。
定理3.6.2的证明 令V1={d(u,v0)偶数―u∈G},V2={d(u,v0)奇数―u∈G}
存在k=f(v6p+2)由性质3.6.2，3.6.3知图Pn3都是平衡二分图。
定理3.6.3的证明 由性质3.6.2知，max{f(V1)}＜min{f(V2)}即图Pn3都是交错图
定理3.7.1对任意自然数K，当n=6k+5图Pn3都是优美图。
(|E|=12k+6
定理3.7.2对任意自然数K，当n=6k+5图Pn3都是平衡二分图。
定理3.7.3对任意自然数K，当n=6k+5图Pn3都是交错图。
我们先给出顶点标号递推算法：
1）设P=v0v1v2v3…vn-1, 图Pn3各顶点的标号如果已给出，依此为v0,v1,v2…vn-1;
2）当n`=6(K+1)+5时，图Pn3各点标号如下：
a) 图Pn`3中的点v0`,v1`,v2`…v6k-2`有v2s`=v2s,v2t+1`=v2t+1+12(2s,2t≤6k+4,s,t,=0,1,2,…)
3）当k=1即n=11时，图Pn3各点标号如图7。
图7
按照以上的递推算法1，对任意自然数k，当n=6k+5时图Pn3具有如下性质，
性质3.7.1图Pn3中的奇点标号从大到小排列。
证明 当k=1时，由图8命题成立；
假设k=p时，即n=6p+5时命题成立；
性质3.7.2图Pn3中的奇点标号都比所有偶点的标号大。
证明当k=1时，由图8命题成立
假设当k=p时，即n=6p+5时命题成立即有v6p+3＞v2s(2s≤6p+4,s=0,1,2,…)
当k=p+1时即n`=6(p+1)+5时，由算法中b)有v6p+9`＞v6p+10` ＞v6p+8`＞v6p+6`又由假设及性质3.7.1知，命题成立。
3.7.3 图Pn3中的偶点标号从小到大排列。
证明当k=1即n=11显然命题成立
假设k=p时，即n=6p+5时命题成立 即v0＜v2＜v4＜…＜v6p+4
当k=p+1时即n`=6(p+1)+5时，由算法中a)及假设有v0`=v0＜v2`=v2＜…＜v6p+4`又由b）及假设得命题成立。
性质3.7.4图Pn3中的所有的顶点的标号各不相同，即f:V(Pn3){0,1,2,…12k+6}是单射。
证明由算法及性质3.7.1，3.7.2，3.73可知，f是单射。
性质3.7.5 图Pn3中的所有的边的标号为{1，2，…12k+6}。
证明当k=1时，即n=11时命题显然成立
定理3.7.1的证明由性质3.7.4，3.7.5，对任意自然数k,当n=6k+5时，图Pn3存在一个优美标号。由定义1，图Pn3优美图。
定理3.7.2的证明 令V1={d(u,v0)偶数―u∈G},V2={ d(u,v0)奇数―u∈G}。
存在k=f(v6p+4)由性质3.7.2，3.7,3知图Pn3都是平衡二分图。
定理3.7.3的证明 由性质3.7.2知，max{f(V1)}＜min{f(V2)}即图Pn3都是交错图。
参考文献：
[1]马克杰.优美图[M]北京：北京大学出版社，1987.
[2]T Gracl. On Sequential Labellings of Graphs[M].Journal of Graph Theory,1983,7:195-210.
[3]曾建华.图的b-优美性[M].经济数学，1999，16（1）：76-78.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。