论文部分内容阅读
摘要: 当n≥2,mi≥3(i=1,2,…,n),圈的路联图P(Cm1,Cm2,…,Cmn)与树联图T(Cm1,Cm2,…,Cmn)均是cordial 图。
关键词:Cordial性;路联图;树联图
中图分类号:O1576 文献标识码:A 文章编号:0000-0129/K(2014)02-0084-03
本文讨论的均为无向有限的简单图。
设f是图G顶点集V(G)的0-1标号,即任给顶点v∈V(G),定义v的标号f(v)=0或f(v)=1。在f条件下,标号为0和1的顶点分别记为V0(G,f)和V1(G,f),用符号v0(G,f)和v1(G,f)分别记二者的基数。由顶点的标号f导出边标号:f(uv)=|f(u)-f(v)|。显然,边的标号取值只能是0和1。标号为0、1的边集分别记为E0(G,f)、E1(G,f),它们的基数记作e0(G,f)、e1(G,f)。显然,上述所有的定义与标号f有关。有时在不引起混淆的情况下,f可省略。以后将标号为i(i=0,1)的顶点、边分别简称为i点、i边。
定义1① ②: 若图G的标号f如上定义,且满足:
(1):|v0(G,f)-v1(G,f)|≤1 ;
(2):|e0(G,f)-e1(G,f)|≤1 ;
则称标号f是图G的cordial标号。存在cordial标号的图称为cordial图,或具有cordial性。
定义2③ ④: G1,G2,…,Gn(n≥2)是一系列简单图,Gi与Gi+1(i=1,2,…,n-1)有且仅有一边相连,此边的两端点分别是图Gi与Gi+1的任意顶点,如此作法得到的图称为G1,G2,…,Gn的路联图(Path-union),记为P(G1,G2,…,Gn)。若G=G1=G2=…=Gn,可简写为P(G)或G(n )。
定义3⑤: G1,G2,…,Gn(n≥2)是一系列简单图,对于任一顶点数为n的树T,其n个顶点分别为v1,v2,…,vn。若vivj(1≤i,j≤n)为树T的边,则在图Gi,Gj中各取一点并在这两点添上一条边,如此作法得到的图称为G1,G2,…,Gn的树联图(tree-union),记为T(G1,G2,…,Gn)。若G=G1=G2=…=Gn,可简写为T(G)。由定义可知,路联图是树联图的特殊情况。
Shee 和Ho 在文献③中已给出这样的结论:当n≥2,m≥3,Cm(n)是cordial图。本文对此结论进行推广,将讨论当n≥2,mi≥3(i=1,2,…,n),P(Cm1,Cm2,…,Cmn)与T(Cm1,Cm2,…,Cmn)的cordial 性。
引理1: G是任一cordial 图,则在G的任一顶点v路联C3、C4、C5、C6,所得到的图G*均还是cordial 图。
证明:由于G是cordial 图,则必存在cordial标号f使得|v0(G,f)-v1(G,f)|≤1 、|e0(G,f)-e1(G,f)|≤1成立。不妨设f(v)=0,根据路联的圈的顶点数不同分以下四种情形:
Case 1:G路联C3;构造G*的标号:G*中图G的标号不变;若V0(G,f)≤V1(G,f),C3可按图(1)标号;若V0(G,f)>V1(G,f),C3按图(2)标号。记此标号为f*,由标号可知|V0(G*,f*)-V1(G*,f*)|≤1 、|e0(G*,f*)-e1(G*,f*)|≤1。故G路联C3仍是cordial 图。
Case 2:G路联C4;构造G*的标号:G*中图G的标号不变;若e0(G,f)≤e1(G,f),C4可按图(3)标号;若e0(G,f)>e1(G,f),C4按图(4)标号。记此标号为f*,由标号可知|v0(G*,f*)-v1(G*,f*)|≤1 、|e0(G*,f*)-e1(G*,f*)|≤1。故G路联C4仍是cordial 图。
Case 3:G路联C5;构造G*的标号:G*中图G的标号不变;若v0(G,f)≤v1(G,f),C5可按图(5)标号;若v0(G,f)>v1(G,f),C5按图(6)标号。记此标号为f*,由标号可知|v0(G*,f*)-v1(G*,f*)|≤1 、|e0(G*,f*)-e1(G*,f*)|≤1。故G路联C5仍是cordial 图。
Case 4:G路联C6;构造G*的标号:G*中图G的标号不变;若e0(G,f)≤e1(G,f),C6可按图(7)标号;若e0(G,f)>e1(G,f),C6按图(8)标号。记此标号为f*,由标号可知|v0(G*,f*)-v1(G*,f*)|≤1 、|e0(G*,f*)-e1(G*,f*)|≤1。故G路联C6仍是cordial 图。
引理2:任给两个整数i、j,且3≤i,j≤6,则Ci路联Cj是cordial 图。
证明:由C3、C4、C5是cordial 图及引理1,可得Ci(i=3,4,5)路联Cj(j=3,4,5,6)仍是cordial 图。现只需证明C6(2)是cordial 图即可。下图(9)给出C6(2)的一个cordial标号。综上引理2得证。
引理3:G是任一cordial 图,uv∈E(G),则在边uv上添加4个剖分点,依次为a、b、c、d,所得到的图G*仍是cordial 图。
由引理3可直接得:
性质1:若Cm是cordial 图,则Cm+4k(k∈N)仍是cordial 图。
根据引理1、引理3,我们可得到以下结论:
定理1:当n≥2,mi≥3(i=1,2,…,n),T(Cm1,Cm2,…,Cmn)是cordial 图。
证明:对n作归纳。当n=2时,即由Cm1,Cm2两个圈路联而成。不论m1、m2取何值,利用性质1都可转化为Ci和Cj (3≤i,j≤6)的路联。而引理2证明了Ci和Cj (3≤i,j≤6)的路联是cordial 图。故Cm1与Cm2的树联是cordial 图。
假设当n=k时,定理成立,即T(Cm1,Cm2,…,Cmk)是cordial 图。
当n=k+1,根据树至少存在两个一度点的性质,故必存在两个圈有且仅有一边相连,不妨设为圈Cmk,Cmk+1。对于圈Cmk+1必存在整数i、l,使得mk+1=4l+i(i=3,4,5,6) 。利用假设和引理1,知T(Cm1,Cm2,…,Cmk,Ci)是cordial 图。根据引理3,就得T(Cm1,Cm2,…,Cmk,Cmk+1)是cordial 图。综上定理得证。
由定理1,显然有:
定理2:当n≥2,mi≥3(i=1,2,…,n),P(Cm1,Cm2,…,Cmn)是cordial 图。
注释:
① 张升,堵根民圈轮的cordial性[J]内蒙古师范大学学报(自然科学汉文版),1999,(04):7-11
② ICahit,cordial graphs: a weaker version of graceful and harmonious graphs,Ars Combin,23(1987) 201-207
③ SCShee and YSHo, the cordiality of the path-union of n-copies of a graph,Discrete Math,117(1993): 225-243
④ Joseph A Gallian,a dynamic survey of graph labeling,The Electronic Journal of Combinatorics,5(2005):41-46
Abstract:The path-union of the graphsP(Cm1,Cm2,…,Cmn)and the tree-union of the graphsT(Cm1,Cm2,…,Cmn)are cordial for n≥2 and mi≥3(i=1,2,…,n).
Key words:Cordial; Path-union; Tree-union
【责任编辑 罗 雪】
关键词:Cordial性;路联图;树联图
中图分类号:O1576 文献标识码:A 文章编号:0000-0129/K(2014)02-0084-03
本文讨论的均为无向有限的简单图。
设f是图G顶点集V(G)的0-1标号,即任给顶点v∈V(G),定义v的标号f(v)=0或f(v)=1。在f条件下,标号为0和1的顶点分别记为V0(G,f)和V1(G,f),用符号v0(G,f)和v1(G,f)分别记二者的基数。由顶点的标号f导出边标号:f(uv)=|f(u)-f(v)|。显然,边的标号取值只能是0和1。标号为0、1的边集分别记为E0(G,f)、E1(G,f),它们的基数记作e0(G,f)、e1(G,f)。显然,上述所有的定义与标号f有关。有时在不引起混淆的情况下,f可省略。以后将标号为i(i=0,1)的顶点、边分别简称为i点、i边。
定义1① ②: 若图G的标号f如上定义,且满足:
(1):|v0(G,f)-v1(G,f)|≤1 ;
(2):|e0(G,f)-e1(G,f)|≤1 ;
则称标号f是图G的cordial标号。存在cordial标号的图称为cordial图,或具有cordial性。
定义2③ ④: G1,G2,…,Gn(n≥2)是一系列简单图,Gi与Gi+1(i=1,2,…,n-1)有且仅有一边相连,此边的两端点分别是图Gi与Gi+1的任意顶点,如此作法得到的图称为G1,G2,…,Gn的路联图(Path-union),记为P(G1,G2,…,Gn)。若G=G1=G2=…=Gn,可简写为P(G)或G(n )。
定义3⑤: G1,G2,…,Gn(n≥2)是一系列简单图,对于任一顶点数为n的树T,其n个顶点分别为v1,v2,…,vn。若vivj(1≤i,j≤n)为树T的边,则在图Gi,Gj中各取一点并在这两点添上一条边,如此作法得到的图称为G1,G2,…,Gn的树联图(tree-union),记为T(G1,G2,…,Gn)。若G=G1=G2=…=Gn,可简写为T(G)。由定义可知,路联图是树联图的特殊情况。
Shee 和Ho 在文献③中已给出这样的结论:当n≥2,m≥3,Cm(n)是cordial图。本文对此结论进行推广,将讨论当n≥2,mi≥3(i=1,2,…,n),P(Cm1,Cm2,…,Cmn)与T(Cm1,Cm2,…,Cmn)的cordial 性。
引理1: G是任一cordial 图,则在G的任一顶点v路联C3、C4、C5、C6,所得到的图G*均还是cordial 图。
证明:由于G是cordial 图,则必存在cordial标号f使得|v0(G,f)-v1(G,f)|≤1 、|e0(G,f)-e1(G,f)|≤1成立。不妨设f(v)=0,根据路联的圈的顶点数不同分以下四种情形:
Case 1:G路联C3;构造G*的标号:G*中图G的标号不变;若V0(G,f)≤V1(G,f),C3可按图(1)标号;若V0(G,f)>V1(G,f),C3按图(2)标号。记此标号为f*,由标号可知|V0(G*,f*)-V1(G*,f*)|≤1 、|e0(G*,f*)-e1(G*,f*)|≤1。故G路联C3仍是cordial 图。
Case 2:G路联C4;构造G*的标号:G*中图G的标号不变;若e0(G,f)≤e1(G,f),C4可按图(3)标号;若e0(G,f)>e1(G,f),C4按图(4)标号。记此标号为f*,由标号可知|v0(G*,f*)-v1(G*,f*)|≤1 、|e0(G*,f*)-e1(G*,f*)|≤1。故G路联C4仍是cordial 图。
Case 3:G路联C5;构造G*的标号:G*中图G的标号不变;若v0(G,f)≤v1(G,f),C5可按图(5)标号;若v0(G,f)>v1(G,f),C5按图(6)标号。记此标号为f*,由标号可知|v0(G*,f*)-v1(G*,f*)|≤1 、|e0(G*,f*)-e1(G*,f*)|≤1。故G路联C5仍是cordial 图。
Case 4:G路联C6;构造G*的标号:G*中图G的标号不变;若e0(G,f)≤e1(G,f),C6可按图(7)标号;若e0(G,f)>e1(G,f),C6按图(8)标号。记此标号为f*,由标号可知|v0(G*,f*)-v1(G*,f*)|≤1 、|e0(G*,f*)-e1(G*,f*)|≤1。故G路联C6仍是cordial 图。
引理2:任给两个整数i、j,且3≤i,j≤6,则Ci路联Cj是cordial 图。
证明:由C3、C4、C5是cordial 图及引理1,可得Ci(i=3,4,5)路联Cj(j=3,4,5,6)仍是cordial 图。现只需证明C6(2)是cordial 图即可。下图(9)给出C6(2)的一个cordial标号。综上引理2得证。
引理3:G是任一cordial 图,uv∈E(G),则在边uv上添加4个剖分点,依次为a、b、c、d,所得到的图G*仍是cordial 图。
由引理3可直接得:
性质1:若Cm是cordial 图,则Cm+4k(k∈N)仍是cordial 图。
根据引理1、引理3,我们可得到以下结论:
定理1:当n≥2,mi≥3(i=1,2,…,n),T(Cm1,Cm2,…,Cmn)是cordial 图。
证明:对n作归纳。当n=2时,即由Cm1,Cm2两个圈路联而成。不论m1、m2取何值,利用性质1都可转化为Ci和Cj (3≤i,j≤6)的路联。而引理2证明了Ci和Cj (3≤i,j≤6)的路联是cordial 图。故Cm1与Cm2的树联是cordial 图。
假设当n=k时,定理成立,即T(Cm1,Cm2,…,Cmk)是cordial 图。
当n=k+1,根据树至少存在两个一度点的性质,故必存在两个圈有且仅有一边相连,不妨设为圈Cmk,Cmk+1。对于圈Cmk+1必存在整数i、l,使得mk+1=4l+i(i=3,4,5,6) 。利用假设和引理1,知T(Cm1,Cm2,…,Cmk,Ci)是cordial 图。根据引理3,就得T(Cm1,Cm2,…,Cmk,Cmk+1)是cordial 图。综上定理得证。
由定理1,显然有:
定理2:当n≥2,mi≥3(i=1,2,…,n),P(Cm1,Cm2,…,Cmn)是cordial 图。
注释:
① 张升,堵根民圈轮的cordial性[J]内蒙古师范大学学报(自然科学汉文版),1999,(04):7-11
② ICahit,cordial graphs: a weaker version of graceful and harmonious graphs,Ars Combin,23(1987) 201-207
③ SCShee and YSHo, the cordiality of the path-union of n-copies of a graph,Discrete Math,117(1993): 225-243
④ Joseph A Gallian,a dynamic survey of graph labeling,The Electronic Journal of Combinatorics,5(2005):41-46
Abstract:The path-union of the graphsP(Cm1,Cm2,…,Cmn)and the tree-union of the graphsT(Cm1,Cm2,…,Cmn)are cordial for n≥2 and mi≥3(i=1,2,…,n).
Key words:Cordial; Path-union; Tree-union
【责任编辑 罗 雪】