关于笛卡尔乘积图的优美性

关于笛卡尔乘积图的优美性

刘家保,邹婷,陆一南

【摘 要】摘要：研究了笛卡尔乘积图Pm×Pn×P1的优美标号算法,并且给出了他们都是优美图的证明,同时推广了笛卡尔乘积图Pm×Pn是优美图的结论. 【期刊名称】纯粹数学与应用数学 【年(卷),期】2012(028)003 【总页数】5

【关键词】优美标号;优美图;笛卡尔乘积图

1 引言

优美图是图论中极其有趣的内容,是一类特殊的简单无向图.优美图的优美标号可应用于编码理论、通信网络、射电天文学、导弹控制码设计等方面,一直以来深受人们的重视,迄今,已有许多这方面的成果[14].但由于对优美图的研究缺一个系统而有力的工具,所以目前只能对一些特殊的图类探索其优美性.

图的优美标号问题由于其趣味性及较好的研究前景和应用价值,其研究十分活跃[58],也有许多结果,但对于笛卡尔乘积图的优美标号的研究结果很少.文献[9]中研究了笛卡尔乘积图Pm×Pn的奇优美性和奇强协调性.文献[10]中证明了Pm×Pn是优美的.本文研究了由笛卡尔乘积得到的图Pm×Pn×P1的优美性问题,并得到了这类图优美标号的算法,并给出了相应的优美性的证明,从而得到了这类图是优美图的结论,推广了笛卡尔乘积图Pm×Pn是优美图的结论. 下面介绍一些基本的概念和符号,其他未加说明的术语和符号请参见文献[1]. 定义1.1对于一个图G=(V,E),如果对每个顶点v∈V,存在一个非负整数L(v)(称为顶点v的一个标号)满足: