P2×Cn的友好标号集

尤永旦 华 波

(1.浙江师范大学 数理与信息工程学院，浙江 金华321004;2.东华大学 理学院，上海201620)

0 引言

设图G是一个简单图，由点的标号函数f:V→Z2,可以诱导出边的标号函数f*:E→Z2，使得f*xy=fx+fymod2,∀xy∈EG.对任意一个i∈Z2，定义vfi=f-1i和efi=f*-1i.如果vf1-vf0≤1，称标号函数f:V→Z2为友好标号函数.我们定义友好指数FI和全友好指数FFI指数如下:

FIG=ef1-ef0f是图G的一个友好标号函数，

1 预备知识

定义1.1[1]：给定两个图G=V,E和H=V',E'，定义G×H=V×V',E''如下：

E''=v,v',u,u':v.u∈E且v'=u'或者v=u且v'.u'∈E'.

引理1.1[2]：Cm中有i个顶点赋值为1，不妨设1≤2i≤m，用参考文献[2]求解的方法可知ef1可以取2,4,…,2i.此处的f未必是友好标号函数.

引理1.2：设f是P2×Cn的一个友好标号函数，当n=2k时候，ef1为偶数，反之，ef1为奇数.

证明：i,j边有两个顶点：一个赋值为i另外一个赋值为j，i,j∈0,1.由引理1.1可知P2×Cn中的两个圈Cn的ef1为偶数只要证明两个圈Cn之间的边ef1的奇偶性就行.现在考虑设两个圈Cn之间的边ef1的奇偶性，设在其中一个圈Cn中点赋值为1有i,其中2i≤n，在这个Cn中点赋值为0有n-i，在另外一个圈Cn中点赋值为1有n-i，并且点赋值为0有i，设两圈之间有j条1,1边其中j≤mini,n-i，则就会也有j条0,0边，所以在这个两个圈之间的0,1边的边数为n-2j，所以引理1.2成立.

引理1.3：

当n≡0mod4时，FIP2×Cn⊆3n,3n-4,…,8,4,0，

当n≡2mod4时，FIP2×Cn⊆3n,3n-4,…,10,6,2，当n=2k+1时，FIP2×Cn⊆3n,3n-2,…,5,3,1.

证明：显然ef1+ef0=EP2×Cn=3n.

因此得知当n≡0mod4时，FIP2×Cn⊆3n,3n-4,…,8,4,0，

当n≡2mod4时，FIP2×Cn⊆3n,3n-4,…,10,6,2，

根据引理1.2，当n=2k+1时候，ef1为奇数，同理可知当n≡2k+1，FIP2×Cn⊆3n,3n-2,…,5,3,1.

2 主要结果

定理2.1：

当n≡0mod4时，FIP2×Cn=3n,3n-8,3n-12,…,8,4,0，

当n≡2mod4时，FIP2×Cn=3n,3n-8,3n-12,…,10,6,2当n=2k+1时，FIP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

证明：

若n=2j，由引理1.2可知在图P2×Cn中ef1为偶数.当f是友好标号函数时，则在图P2×Cn中ef1为偶数.且可证ef1取到大部分偶数，证明如下：

构造使得ef1=4的友好标号函数

构造使得ef1=3n的友好标号函数

e1可取到4,6,8,…,2n-2,2n,3n,

可证P2×Cn中ef1≠2.

若有两个圈C1=u1,1u1,2u1,3…u1,n，C2=u2,1u2,2u2,3…u2,n的边赋值都为0，则根据友好标号函数可知两个圈的点赋值一个赋值为0，另外一个赋值为1，则ef1=n≥4，若有一个圈(不妨设为C1=u1,1u1,2u1,3…u1,n)中有边赋值为1，因为圈边赋值为1为偶数所以这个圈中边赋值至少为偶数，又根据友好标号函数，则在另外一个圈中必然也是边赋值1的条也是偶数并且在这个圈中ef1≥2，所以在P2×Cn中ef1≠2.

又可证P2×Cn中ef0≠2.

第一种情形若ef0=2的边全在圈C1中，则边赋值为0的边(不妨设边u1,iu1,i+1)必然与下面一个圈C2中u2,i，u2,i+1两点组成一个小圈，则可得出在这个小圈中ef0=2或者4.同理在另外一个小圈ef0=2或者4，则就会出现ef0≠2，假设矛盾.

第二种情形ef0=2都不在圈C1，C2中不妨设边u1,iu2,i，u1,ju2,j，1+i≤j为1，圈C3=u1,iu2,iu2,i-1u1,i-1这样可知道是在圈C3,圈C4与圈C5=u1,iu2,iu2,i+1…u

2,ju1,ju1,j-1u1,j-2…u1,i+1，1+i≤j中每个圈的ef0至少为2，所以得出ef0≠2与假设矛盾.因为

ef1≠2,ef0≠2可知3n-4∉FIP2×Cn.因为e1=4,6,8,…,2n-2,2n,3n，e1≠2,e0≠2，再根据根据引理1.3,所以当n≡2mod4时，FIP2×Cn=3n，3n-8,3n-12,…,8,4,0.

当n≡2mod4时，FIP2×Cn=3n，3n-8,3n-12,…,10,6,2.

断言1：若n=2j+1，则在图P2×Cn中ef1为取到大部分奇数.证明如下：

由引理1.2在图P2×Cn中e1为奇数，构造使得ef1=5的友好标号函数

构造使得ef1=7的友好标号函数

现在已经构造友好标号函数使得e1=5,7,…,2n+1,

这样就有ef0=2,4,…,n-1，根据ef1+ef0=EP2×Cn=3n，可知ef1=3n-2,3n-4,…,2n+1,所以我们已经构造出ef1=5,7,…,2n+1,…,3n-4,3n-2.

断言2：ef1≠1，其中f为P2×Cn的友好标号函数.

若在P2×Cn中ef1=1，边赋值为1在下面C1=u1,1u1,2u1,3…u1,n，C2=u2,1u2,2u2,3…u2,n中的某个圈中，不妨设C1=u1,1u1,2u1,3…u1,n，则根据引理1.1可知边赋值为1至少两条，与假设矛盾，若都不在这两个圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n，则边赋值为1在圈C1与圈C2之间的连接处，不妨设点u1,1=0，u2,1=1，则在C3=u1,1u2,1u2,2u1,2中，根据引理2.1可知边赋值为1至少两条，所以P2×Cn中ef1≠1.

断言3：当n≥5时，ef1≠3，其中f为P2×Cn的友好标号函数.

若有两个圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n边赋值为都为0，则根据友好标号函数可知C1=u1,1u1,2u1,3…u1,n的点都赋值为0，C2=u2,1u2,2u2,3…u2,n的点都赋值为1；或者C1=u1,1u1,2u1,3…u1,n的点都赋值为1，C2=u2,1u2,2u2,3…u2,n的点都赋值为0，则e1=n≥5.

若有一个圈C1=u1,1u1,2u1,3…u1,n中边赋值为1，根据引理1.1可知圈边赋值为1的边数为偶数，所以在这个圈C1中ef1≥2，又根据友好标号函数，则在C2=u2,1u2,2u2,3…u2,n中必然也是边赋值1且为偶数条，而且在这个圈C2中ef1≥2，所以ef1≥4≠3.

断言4：ef0≠1ef0≠3，其中f为P2×Cn的友好标号函数.

因为由引理1.2可知e1为奇数，所以可知在该图中e0为偶数，所以e0≠1e0≠3明显成立.

当n=2k+3时，k∈1,2,3,…，因为e1=5,7,9,…,2n-7,…,3n-2，

e1≠3,e0≠3，e1≠1,e0≠1,显然这个等式e1=3n不成立(由引理1.1可知在奇圈中e1也是偶数而e1=3n这个是奇数).

当n=2k+3，n∈1,2,3,…时，FIP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

当n=3时，ef1≠1，ef1≠3n=9，ef1=3,5,7，所以FIP2×C3=5,3,1.

所以当n=2k+1时，FIP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

参考文献：

[1]J A Bandy, U S R Murty.Graph Theory with Application[M].Springer International Publisher,2007.

[2] N Cairnie ， K Edwards.The computational complexity of cordial and equitable labeling[J].Discrete Math,2000,216:29-34.

Abstract： Friendly index set is a common problem in the labeling problem. The present paper researches the friendly index set of graphP2×Cn.

Keywords：friendly labeling function; FI; FFI; circle