APP下载

一类二部图生成的广义格子图的邻点可区别边染色

2014-03-02刘信生刘元元

关键词:邻点拷贝阶数

刘信生,缑 艳,姚 兵,刘元元

(西北师范大学数学与统计学院,甘肃 兰州730070)

1 预备知识

图的染色问题是图论的重要研究内容之一,具有重要的理论价值和实际意义.由不同实际问题引出了不同的染色概念,如仓库数的研究、地图染色、有线通信网、无线通信网等引出的邻点可区别边染色问题,得到国内外图论研究者的关注.近些年来,虽然许多学者在这一领域已经取得了很多成果[1-8],但这方面的研究工作尚属开始,许多猜想的解决处于特殊图的验证阶段.本文定义了一类2维广义格子图H2(G,n,m;k1,k2),且通过从图的结构出发,利用构造染色的方法,得到了图H2(Kp,p,n,m;p,p)的邻点可区别边色数.从而验证了邻点可区别边色数猜想.

定义1[1]设G(V,E)是阶数至少为3的简单连通图,k-是正整数.若G(V,E)是一个k-正常边染色f 满足:∀uv∈E(G),S(u)≠S(v),其中S(u)={f(uv)|uv∈E(G)},则称f 为G 的一个k-邻点可区别边染色,简记为k-AVDPEC,且称χ′a(G)=min{k|G 存在k-AVDPEC}为G 的邻点可区别边色数.

猜想[1]设图G 是阶数至少为3的简单连通图,若G≠C5,则χ′a(G)≤Δ+2.

定义2 把一个根图G 做n 个拷贝,记做G(1),G(2),…,G(n).连接每相邻两个G(i)与G(i+1)(i=1,2,…,n-1)间的k1对顶点,所得的图记做H1(G,n;k1),并称为1 维广义格子图,见图1.然后把H1(G,n;k1)做m 个拷贝,记做H(1)1(G,n;k1),H(2)1(G,n;k1),…,H(m)1(G,n;k1).将H(j)1(G,n;k1)中的每个根图记为G(1,j),G(2,j),…,G(n,j)(j=1,2,…,m).连接G(i,j)与G(i,j+1)(i=1,2,…,n;j=1,2,…,m-1)间的k2对顶点,所得的图记做H2(G,n,m;k1,k2),并称为2维广义格子图,见图2.

注 定义2中的2维广义格子图不难推广到t维广义格子图Ht(G,n1,n2,…,nt;k1,k2,…,kt).

图1 1维广义格子图H1(G,n;k1)

引理1[1]对阶数不小于3的简单连通图G,有χ′a(G)≥Δ.若G 中存在相邻的最大度点,则

其他的相关术语和记号,可参见文献[9].

图2 2维广义格子图H2(G,n,m;k1,k2)

2 主要结果

定理1 对n≥3,m≥3,有χ′a(H2(Kp,p,n,m;p,p))=p+6.

证明 把根图Kp,p做n 个 拷 贝,记 做Kp(1,p),Kp(2,p),…,Kp(n,p).且 记V(Kp(i,)p)=Xi∪Yi,Xi∩Yi=∅,|Xi|=|Yi|=p,其 中Xi={v1(i),v2(i),…,vp(i)},Yi={u1(i),u2(i),…,up(i)}(i=1,2,…,n).连 接vj(i)与vj(i+1),uj(i)与uj(i+1)(i=1,2,…,n-1;j=1,2,…,p)后所得的图记做H1(Kp,p,n;p).然后把H1(Kp,p,n;p)做m 个拷贝,记做H1(1)(Kp,p,n;p),H1(2)(Kp,p,n;p),…,H1(m)(Kp,p,n;p).其中,H1(j)(Kp,p,n;p)中的每个根图记为Kp(1,p,j),Kp(2,p,j),…,Kp(n,p,j)(j=1,2,…,m).且 记V(Kp(i,,pj))=Xi,j∪Yi,j,Xi,j∩Yi,j=∅,|Xi,j|=|Yi,j|=p,其中Xi,j={v1(i,j),v2(i,j),…,vp(i,j)},Yi,j={u1(i,j),u2(i,j),…,up(i,j)}(i=1,2,…,n;j=1,2,…,m).连接vt(i,j)与vt(i,j+1),ut(i,j)与ut(i,j+1)(i=1,2,…,n;j=1,2,…,m-1;t=1,2,…,p)后所得到的图记做H2(Kp,p,n,m;p,p),见图3.

图3 2维广义格子图H2(Kp,p,n,m;p,p)

由于图H2(Kp,p,n,m;p,p)中存在相邻的最大度顶点,且Δ(H2(Kp,p,n,m;p,p))=p+4,由引理1可知,χ′a(H2(Kp,p,n,m;p,p))≥p+5,如果χ′a(H2(Kp,p,n,m;p,p))=p+5,那么不失一般性,可设(在这里,我们用(u)表示S(u)在颜色构成的集合{1,2,…,p+6}中的补集).那么点vt(i,j)的所有邻点的补集合里都必须包含色q.由于无论p是奇数还是偶数,由图H2(Kp,p,n,m;p,p)的结构可知,这些点中的任意两点之间都只有偶数条边相连,故不存在这p+4个点的完美匹配.因此,用p+5种颜色不能对图H2(Kp,p,n,m;p,p)进行邻点可区别边染色,故χ′a(H2(Kp,p,n,m;p,p))≥p+6,为证χ′a(H2(Kp,p,n,m;p,p))=p+6,只需给出H2(Kp,p,n,m;p,p)的一个p+6-AVDPEC即可.我们分两种情况来证明结论.

情况Ⅰ 当p≡1(mod 2)时,分以下四个步骤给出具体染色f:

ⅰ 对拷贝H1(1)(Kp,p,n;p)的边进行染色,令f 为:

当h≡1(mod 2)时,f(vi(h,1)uj(h,1))=[j+2(i-1)]p+2(i=1,2,…,p;j=1,2,…,p;h=1,2,…,n).

当h≡0(mod 2)时,f(vi(h,1)uj(h,1))=[j+2(j-1)]p+2(i=1,2,…,p;j=1,2,…,p;h=1,2,…,n).

ⅱ 对拷贝H1(2)(Kp,p,n;p)的边进行染色,令f 为:

当h≡1(mod 2)时,f(vi(h,1)uj(h,1))=[j+2(j-1)]p+2(i=1,2,…,p;j=1,2,…,p;h=1,2,…,n).

当h≡0(mod 2)时,f(vi(h,1)uj(h,1))=[j+2(i-1)]p+2(i=1,2,…,p;j=1,2,…,p;h=1,2,…,n).

ⅲ 拷贝H(j)1(Kp,p,n;p)(j≡1(mod 2)且3≤j≤m)的边染色与H(1)1(Kp,p,n;p)的边染色完全一致,拷贝H(j)1(Kp,p,n;p)(j≡0(mod 2)且4≤j≤m)的边染色与H(2)1(Kp,p,n;p)的边染色完全一致.

ⅳ 对每相邻两个拷贝H(j)1(Kp,p,n;p)与H(j+1)1(Kp,p,n;p)(1≤j≤m-1)之间的边进行染色,令f 为:

下证明以上染色是邻点可区别的:

由图H2(Kp,p,n,,m;p,p)的结构可知,只需证明中的各顶点是邻点可区别的即可.因此,当i≡0(mod 2)且j≡0(mod 2)或当i≡1(mod 2)且j≡1(mod 2)时,对f 有当i≡0(mod 2)且j≡1(mod 2)或当i≡1(mod 2)且j≡0(mod 2)时,对f有

综上,易看出当p≡1(mod 2)时,图H2(Kp,p,n,m;p,p)中任意相邻两顶点的色集合均不同,故f是图H2(Kp,p,n,m;p,p)的一个p+6-AVDPEC.且满足邻点可区别边色数猜想.

情况Ⅱ 当p≡0(mod 2)时,分以下四个步骤给出具体染色f:

ⅰ 对拷贝H(1)1(Kp,p,n;p)的边进行染色,令f 为:

ⅱ 对拷贝H(2)1(Kp,p,n;p)的边进行染色,令f 为:

ⅲ 拷贝H(j)1(Kp,p,n;p)(j≡1(mod 2)且3≤j≤m)的边染色与H(1)1(Kp,p,n;p)的边染色完全一致,拷贝H(j)1(Kp,p,n;p)(j≡0(mod 2)且4≤j≤m)的边染色与H(2)1(Kp,p,n;p)的边染色完全一致.

ⅳ对每相邻两个拷贝H(j)1(Kp,p,n;p)与H(j+1)1(Kp,p,n;p)(1≤j≤m-1)之间的边进行染色,令f为:

下面证明以上染色是邻点可区别的:

由图H2(Kp,p,n,,m;p,p)的结构可知,只需证明中的各顶点是邻点可区别的即可.因此,当i≡0(mod 2)且j≡0(mod 2)或当i≡1(mod 2)且j≡1(mod 2)时,对f 有且且6≤t≤p.当i≡0(mod 2)且j≡1(mod 2)或当i≡1(mod 2)且j≡0(mod 2)时,对f 有且0(mod 2)且

综上,易看出当p≡0(mod 2)时,图H2(Kp,p,n,m;p,p)中任意相邻两顶点的色集合均不同,故f是图H2(Kp,p,n,m;p,p)的一个p+6-AVDPEC,且满足邻点可区别边色数猜想.

猜你喜欢

邻点拷贝阶数
路和圈、圈和圈的Kronecker 积图的超点连通性∗
围长为5的3-正则有向图的不交圈
确定有限级数解的阶数上界的一种n阶展开方法
一个含有五项的分数阶混沌系统的动力学分析
最大度为6的图G的邻点可区别边色数的一个上界
唐氏综合征是因为“拷贝”走样了
复变函数中孤立奇点的判别
关于广义θ—图的邻点可区别染色的简单证明
文化拷贝应该如何“拷”
基于硬盘还原卡的数据传送技术在高校网络机房中的应用