论文部分内容阅读
摘要： 当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
【责任编辑 罗 雪】