APP下载

P2×Cn的友好标号集

2013-12-19尤永旦

关键词:断言小圈标号

尤永旦 华 波

(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

猜你喜欢

断言小圈标号
von Neumann 代数上保持混合三重η-*-积的非线性映射
C3-和C4-临界连通图的结构
Top Republic of Korea's animal rights group slammed for destroying dogs
米小圈小漫画
米小圈
非连通图2D3,4∪G的优美标号
米小圈小漫画
路、圈的Mycielskian图的反魔术标号
非连通图D3,4∪G的优美标号
非连通图(P1∨Pm)∪C4n∪P2的优美性