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

刘家保,邹婷,陆一南

(安徽新华学院公共课教学部,安徽合肥 230088)

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

刘家保,邹婷,陆一南

(安徽新华学院公共课教学部,安徽合肥 230088)

研究了笛卡尔乘积图Pm×Pn×P1的优美标号算法,并且给出了他们都是优美图的证明,同时推广了笛卡尔乘积图Pm×Pn是优美图的结论.

优美标号;优美图;笛卡尔乘积图

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的一个标号)满足:

(1)∀u,v∈V,如果u/=v,则L(u)/=L(v);

(2)max{L(v)|v∈V}=|E|;

(3)∀e1,e2∈E,如果e1/=e2,则L′=|L(u)-L(v)|,e=uv;

那么称图G为优美图,L称为图G的一个优美标号,L′称为由L导出的边标号[3].

定义1.2设Pm、Pn、Pl分别是长度为m、n、l的简单通路,图Pm×Pn×Pl表示由Pm、Pn、Pl经过笛卡尔乘积运算得到的图,记为Pm×Pn×Pl.

2 主要结果及证明

定理2.1当m=l=1时,对任意正整数n,图P1×Pn×P1是优美图.

下面给出图P1×Pn×P1各顶点的标号递推算法A如下:

作为例子分别应用定理2.1中算法A给出P1×P3×P1,P1×P4×P1笛卡尔乘积图的优美标号:

图1 P1×P3×P1的优美标号

图2 P1×P4×P1的优美标号

引理2.1按算法A可得,图P1×Pn×P1中各顶点的标号均不相同,即图顶点集与集合{0,1,2,…,8n+4}构成单射.

证明按算法A中的标号算法(1)-(8)将图中各顶点的标号对应集合A,B,C,D,E,F, G,H,分两种情况加以具体分析讨论:

情况一当n≡0(mod 2)时:

情况二当n≡0(mod 2)时:

由以上讨论可知,图P1×Pn×P1顶点集与集合{1,2,…,8n+4}构成单射.

引理2.2图P1×Pn×P1中各边的标号均不相同,即图P1×Pn×P1的边集与集合{1,2,…,8n+4}构成一一对应.

证明由引理2.1,显然有P1×Pn×P1图中各边的标号都不超过8n+4.由算法A知,图P1×Pn×P1的边标号为集合{1,2,…,8n+4},而图P1×Pn×P1共有8n+4条边,从而所有不同的边有不同的标号.

综上所述,L′是从图P1×Pn×P1的边集到集合{1,2,…,8n+4}的一个双射.

由引理2.1、引理2.2和优美图的定义,当m,n∈ℕ且m=1,n≥2时,图P1×Pn×P1是优美图.

下面讨论当m,n∈ℕ且m≥2,n为任意自然数时的情况.

定理2.2当m≥2,n∈ℕ时,笛卡尔乘积图Pm×Pn×P1是优美图.

证明采用数学归纳法来证明.由定理2.1,当m=1,n为任意自然数时,图P1×Pn×P1是优美图.

当m≥2,n为任意自然数,设Pm-1×Pn×P1是优美图,Lm-1是它的优美标号,则图Pm×Pn×P1优美标号算法B:

其中i+j≡1(mod 2),i=1,2,…,n+1,j=2m+1,2m+2.

作为例子分别应用定理2.2中算法B给出P3×P2×P1、P2×P3×P1笛卡尔乘积图的优美标号:

图3 P3×P1×P1的优美标号

图4 P2×P3×P1的优美标号

引理2.3按算法B可得,图Pm×Pn×P1中各顶点的标号均不相同,即图Pm×Pn×P1顶点集与集合{0,1,2,…,12n+6}构成单射.

证明证明类似引理2.1,此略.

引理2.4图Pm×Pn×P1中各边的标号均不相同,即图Pm×Pn×P1的边集与集合{1,2,…,12n+6}构成一一对应.

证明证明类似引理2.2,此略.

由引理2.3、引理2.4和优美图的定义,容易得到,当Pm-1×Pn×P1是优美图,Lm-1是它的优美标号,则Lm是图Pm×Pn×P1的优美标号.

综合定理2.1和定理2.2,很容易得到下面的定理.

定理2.3对任意的正整数m,n,笛卡尔乘积图Pm×Pn×P1是优美图.

3 结束语

笛卡尔乘积图Pm×Pn的拓扑结构是二维平面中的网格图,而笛卡尔乘积图Pm×Pn×P1的拓扑结构是由若干个小立方体叠加堆积的的三维空间图.文中笛卡尔乘积图Pm×Pn×P1的优美标号算法及给出了他们优美性的严格数学证明,从而得到了这类图是优美图的结论,把笛卡尔乘积图优美标号从二维推广到三维情景,加强了已有文献的结论.

致谢衷心感谢审稿专家及编辑部对本文提出有益的修改意见.

[1]Gallian A.A dynam ic survey of graph labeling[J].The Electronic Journal of Combinatorics,2000,12:1-95.

[2]胡红亮.图Cn及其r-冠的新的优美标号[J].纯粹数学与应用数学,2010,26(3):454-457.

[3]刘家保,王林.一类优美图的计算机算法[J].汕头大学学报:自然科学版,2011,26(2):23-28.

[4]刘家保,王林.一类图的边幻和标号及其算法[J].汕头大学学报:自然科学版,2011,26(3):29-34.

[5]陈淑贞,周俊梅.关于联图P1∨Pn的K-强优美性[J].数学杂志,2010,30(2):357-362.

[6]刘家保,潘向峰.轮形图和扇形图的优美性[J].安徽大学学报:自然科学版,2009,133(4):11-13.

[7]刘家保,张季.一类新的联图的优美标号算法[J].汕头大学学报:自然科学版,2011,26(1):8-10. [8]郭文富.关于图B(m,n,p)的优美性[J].数学杂志,1995,15(3):345-351.

[9]严谦泰.积图Pm×Pn的奇优美性和奇强协调性[J].系统科学与数学,2010,30(3):341-348.

[10]马克杰.优美图[M].北京:北京大学出版社,1991.

The gracefu lness of Cartesian p roduct graphs

Liu Jiabao,Zou Ting,Lu Yi′nan
(Department of Commom Courses,Anhui Xinhua University,Hefei 230088,China)

In this paper,we study the graceful labeling for Cartesian p roduct graphs Pm×Pn×P1and prove that they are all gracefu l graphs.These theorem s extend the results that Cartesian product graphs Pm×Pnare graceful.

graceful labeling,gracefu l graphs,Cartesian product graphs

O157.5

A

1008-5513(2012)03-0329-04

2011-10-04.

国家自然科学基金(10901001);安徽省高等学校省级自然科学基金(K J2010B076);安徽新华学院质量工程建设(2011tskcx07).

刘家保(1982-),硕士,讲师,研究方向：图论与组合网络.

2010 MSC:05C78