关于k-优优观的讨论

关于k-优优观的讨论

在设计的美丽方面的研究中，许多结论都是基于连通性的，而对非连通性的研究结论很少（见文献）。在这项工作中，我们研究了倾斜图wn和完整图km、图1和k-1之间的非连通性图的美丽关系，并证明了当n为奇时，图wngk-1是美丽的图。当n为偶，接图wn和gk-1是美丽的图，并证明接图km、n和gk-1是美丽的图。以下所讨论的图G(V,E)均为简单无向图,设V=V(G)为图G的顶点集,E=E(G)为图G的边集,|E|为图G的边数,G1∨G2为图G1与G2的联图,G1∪G2为图G1与G2的并图,ˉG为图G的补图,˜Wn为齿轮图,〈G1,G2〉为有根图G1与G2两根粘接而成的图,Km,n为完全二部图,Kn为n个顶点的完全图,Pn为n个顶点的路,Cn为n个顶点的圈,Dm为m个K3恰有1个公共点的风车图.定义1设图G=(V,E),k为正整数,如果存在一个单射f:V→{0‚1‚⋯‚|E|+k-1},使得对所有的边uv∈E,由f′(uv)=|f(u)-f(v)|导出一个双射f′:E→{k‚k+1‚⋯‚|E|+k-1},则称图G是k-优美图,f是G的k-优美标号.1-优美图也称优美图,1-优美标号也称优美标号.定理1设n,k为任意正整数,Gk-1是任意一个边数为k-1的优美图,若n≥3,k≥n,则(ⅰ)图˜Wn是k-优美图;(ⅱ)当n为奇数时,图˜Wn∪Gk-1是优美图;(ⅲ)当n为偶数时,粘接图〈˜Wn,Gk-1〉是优美图.gxix1(ⅰ)设V1(˜Wn)={x0‚x(1)1‚x(1)2‚⋯‚x(1)n;x(2)1‚x(2)2‚⋯‚x(2)n}‚E1=E1(˜Wn)‚|E1|=3n,下面分2种情况讨论.情况1当n≡0(mod2)时,定义图˜Wn的顶点标号g为g(x0)=0g(x(1)i)=3n-i+ki=1‚2‚⋯‚ng(x(2)i)={n+i-1i=1‚2‚⋯‚n2n+ii=n2+1‚n2+2‚⋯‚n下面证明标号g是图˜Wn的k-优美标号.由于0=g(x0)<g(x(2)1)<g(x(2)2)<g(x(2)3)<⋯<g(x(2)n2-1)<g(x(2)n2)<g(x(2)n2+1)<g(x(2)n2+2)<g(x(2)n2+3)<⋯<g(x(2)n-1)<g(x(2)n)<g(x(1)n)<g(x(1)n-1)<g(x(1)n-2)<⋯<g(x(1)3)<g(x(1)2)<g(x(1)1)=3n+k-1故映射g:V1(˜Wn)→{0‚n‚n+1‚⋯‚3n2-1‚3n2+1‚⋯‚2n‚2n+k‚2n+k+1‚⋯‚3n+k-1}是单射.对所有的边uv∈E1,设g′(uv)=|g(u)-g(v)|.对于边标号g′分6部分考虑:①g′(x0x(1)i)=3n-i+k(i=1,2,…,n),当i取遍1,2,…,n时,g′(x0x(1)i)取遍I1={2n+k,2n+k+1,…,3n+k-1};②g′(x(1)ix(2)i)=2(n-i)+k+1(i=1‚2‚⋯‚n2),当i取遍1‚2‚⋯‚n2时,g′(x(1)ix(2)i)取遍I2={2n+k-1,2n+k-3,2n+k-5,…,n+k+5,n+k+3,n+k+1};③g′(x(1)i+1x(2)i)=2(n-i)+k(i=1‚2‚⋯‚n2),当i取遍1‚2‚⋯‚n2时,g′(x(1)i+1x(2)i)取遍I3={2n+k-2,2n+k-4,2n+k-6,…,n+k+4,n+k+2,n+k};④g′(x(1)ix(2)i)=2(n-i)+k(i=n2+1‚n2+2‚⋯‚n),当i取遍n2+1‚n2+2‚⋯‚n时,g′(x(1)ix(2)i)取遍I4={n+k-2,n+k-4,n+k-6,…,k+4,k+2,k};⑤g′(x(1)i+1x(2)i)=2(n-i)+k-1(i=n2+1‚n2+2‚⋯‚n-1),当i取遍n2+1‚n2+2‚⋯‚n-1时,g′(x(1)i+1x(2)i)取遍I5={n+k-3,n+k-5,n+k-7,…,k+5,k+3,k+1};⑥I6=g′(x(1)1x(2)n)=n+k-1.设I=I1+I2+I3+I4+I5+I6,则Ι={k‚k+1‚k+2‚⋯‚k+n-1‚k+n‚k+n+1‚⋯‚k+2n-1‚k+2n‚k+2n+1‚⋯‚3n+k-1}由①—⑥得映射g′:E1(˜Wn)→{k‚k+1‚k+2‚⋯‚3n+k-1}是双射.则当n≡0(mod2)时,图˜Wn是k-优美图.情况2当n≡1(mod2)时,定义图˜Wn的顶点标号g为g(x0)=0g(x(1)1)=3n+k-1g(x(1)2)=3n+k-2g(x(2)1)=3n-2g(x(2)n)=2g(x(1)i)=3n-i+k-1i=3‚4‚⋯‚ng(x(2)i)=n+i-2i=2‚3‚4‚⋯‚n-1下面证明标号g是图W˜n的k-优美标号.由于0=g(x0)<g(xn(2))<g(x2(2))<g(x3(2))<⋯<g(xn-3(2))<g(xn-2(2))<g(xn-1(2))<g(x1(2))<g(xn(1))<g(xn-1(1))<g(xn-2(1))<⋯<g(x4(1))<g(x3(1))<g(x2(1))<g(x1(1))=3n+k-1故映射g:V1(W˜n)→{0‚2‚n‚n+1‚⋯‚2n-3‚3n-2‚2n+k-1‚2n+k‚2n+k+1‚⋯‚3n+k-4‚3n+k-2‚3n+k-1}是单射.对所有的边uv∈E1,设g′(uv)=|g(u)-g(v)|.对于边标号g′分3部分考虑:①g′(x0x1(1))=3n+k-1,g′(x0x2(1))=3n+k-2,g′(x0xi(1))=3n-i+k-1(i=3,4,…,n);②g′(x(1)ixi(2))=2(n-i)+k+1(i=3,4,…,n-1),g′(x1(1)x1(2))=k+1,g′(x2(1)x2(2))=2n+k-2,g′(x(1)nxn(2))=2n+k-3;③g′(xi+1(1)xi(2))=2(n-i)+k(i=2,3,…,n-1),g′(x2(1)x1(2))=k,g′(x1(1)xn(2))=3n+k-3.由于k=g′(x2(1)x1(2))<g′(x1(1)x1(2))<g′(xn(1)xn-1(2))<g′(xn-1(1)xn-1(2))<g′(xn-1(1)xn-2(2))<g′(xn-2(1)xn-2(2))<g′(xn-2(1)xn-3(2))<g′(xn-3(1)xn-3(2))<g′(xn-3(1)xn-4(2))<⋯<g′(x0xn-2(1))<g′(x0xn-3(1))<⋯<g′(x0x4(1))<g′(x0x3(1))<g′(x1(1)xn(2))<g′(x0x2(1))<g′(x0x1(1))=3n+k-1故映射g′:E1(W˜n)→{k‚k+1‚k+2‚⋯‚3n+k-1}是双射.则当n≡1(mod2)时,图W˜n是k-优美图.综上所述,对任意正整数n,k,当n≥3,k≥n时,W˜n是k-优美图.(ⅱ)当n为奇数时,设V2=V2(Gk-1),E2=E2(Gk-1),有|E2|=k-1,h是优美图Gk-1的优美标号,则映射h:V2(Gk-1)→{0‚1‚2‚⋯‚k-1}是单射,映射h′:E2(Gk-1)→{1‚2‚3‚⋯‚k-1}是双射.设V=V(W˜n∪Gk-1)=V1∪V2‚E=(W˜n∪Gk-1)=E1∪E2,有|E|=3n+k-1.下面分2种情形讨论.情形1当n,k同为奇数时,定义图W˜n∪Gk-1的顶点标号f为f(u)=g(u)u∈V1(1)f(v)=h(v)+2n-2v∈V2(2)下面证明标号f是图W˜n∪Gk-1的优美标号.由于g:V1(W˜n)→{0‚2‚n‚n+1‚⋯‚2n-3‚3n-2‚2n+k-1‚2n+k‚2n+k+1‚⋯‚3n+k-4‚3n+k-2‚3n+k-1}是单射,h:V2(Gk-1)→{0‚1‚2‚⋯‚k-1}是单射,由式(1)、式(2)得f(xn-1(2))<f(v)<f(xn(1)).又因为V1∩V2=∅,所以f:V(W˜n∪Gk-1)→{0‚2‚n‚n+1‚⋯‚2n-3‚2n-2‚2n-1‚2n‚2n+1‚⋯‚2n+k-3‚3n-2‚2n+k-1‚2n+k‚2n+k+1‚⋯‚3n+k-4‚3n+k-2‚3n+k-1}是单射.由g,h的定义知g′:E1(W˜n)→{k‚k+1‚k+2‚⋯‚3n+k-1}是双射,h′:E2(Gk-1)→{1‚2‚⋯‚k-1}是双射.当uv∈E1时,f′(uv)=|f(u)-f(v)|=|g(u)-g(v)|=g′(uv),则f′(E1)=g′(E1);当uv∈E2时,f′(uv)=|f(u)-f(v)|=|h(u)+2n-2-(h(v)+2n-2)|=|h(u)-h(v)|=h′(uv),则f′(E2)=h′(E2).又由于f′(E1)∩f′(E2)=∅,f′(E1)∪f′(E2)={1,2,…,k-1,k,k+1,…,3n+k-1},且E=E1∪E2,E1∩E2=∅,所以f′:E(W˜n∪Gk-1)→{1‚2‚3‚⋯‚3n+k-1}是双射.则当n,k同为奇数时,W˜n∪Gk-1是优美图.情形2当n为奇数、k为偶数时,定义图W˜n∪Gk-1的顶点标号f为f(u)=g(u)u∈V1f(v)=h(v)+2n-1v∈V2同理证得:当n为奇数、k为偶数时,W˜n∪Gk-1是优美图.综上所述,n为奇数时,W˜n∪Gk-1是优美图.(ⅲ)设V=V(〈W˜n‚Gk-1〉)=V1∪V2‚E=E(〈W˜n‚Gk-1〉)=E1∪E2,则|E|=3n+k-1.定义粘接图〈W˜n,Gk-1〉的顶点标号f为f(u)=g(u)u∈V1(3)f(v)=h(v)+2nv∈V2(4)下面证明标号f是粘接图〈W˜n,Gk-1〉的优美标号.由于g:V1(W˜n)→{0‚n‚n+1‚⋯‚3n2-1‚3n2+1‚⋯‚2n‚2n+k‚2n+k+1‚⋯‚3n+k-1}是单射,h:V2(Gk-1)→{0‚1‚2‚⋯‚k-1}是单射,由(3)式、(4)式得f(xn(2))≤f(v)<f(xn(1)).又因为f(V1)与f(V2)只有一个等值的顶点,即优美图Gk-1中原始优美标号h(v)=0的顶点v在映射f的作用下有f(v)=f(xn(2)),把W˜n和Gk-1中等值的顶点xn(2)和v当作根,将两根粘接在一起得到粘接图〈W˜n,Gk-1〉,所以f:V(〈W˜n‚Gk-1〉)→{0‚n‚n+1‚⋯‚3n2-1‚3n2+1‚⋯‚2n-1‚2n‚2n+1‚⋯‚2n+k-1‚2n+k‚2n+k+1‚⋯‚3n+k-1}是单射.由g,h的定义知g′:E1(W˜n)→{k‚k+1‚k+2‚⋯‚3n+k-1}是双射,h′:E2(Gk-1)→{1‚2‚⋯‚k-1}是双射.当uv∈E1时,f′(uv)=|f(u)-f(v)|=|g(u)-g(v)|=g′(uv),则f′(E1)=g′(E1);当uv∈E2时,f′(uv)=|f(u)-f(v)|=|h(u)+2n-(h(v)+2n)|=|h(u)-h(v)|=h′(uv),则f′(E2)=h′(E2).又由于f′(E1)∩f′(E2)=∅,f′(E1)∪f′(E2)={1,2,…,k-1,k,k+1,…,3n+k-1},且E=E1∪E2,E1∩E2=∅,所以f′:E(〈W˜n‚Gk-1〉)→{1‚2‚3‚⋯‚3n+k-1}是双射.综上所述,当n为偶数时,粘接图〈W˜n,Gk-1〉是优美图.例1(ⅰ)当n=11,k=12时,W˜11∪(Ρ1∨Ρ6)是优美图,其优美标号如图1所示.(ⅱ)当n=8,k=22时,W˜8与P1∨P5的2-冠的粘接图是优美图,其优美标号如图2所示(实心点·为图的根,将两根粘接).定理2设m,n,k为任意正整数,Gk-1是任意一个边数为k—1的优美图.若k≥2,则(ⅰ)图Km,n是k-优美图;(ⅱ)粘接图〈Km,n,Gk-1〉是优美图.k-佳合图的类型(ⅰ)设V1(Km,n)=V′1∪V′2,|V′1|=m,|V′2|=n,E1=E1(Km,n),|E1|=mn.定义图Km,n的顶点标号g为g(vi)=i-1vi∈V′1‚i=1‚2‚⋯‚mg(uj)=jm+k-1uj∈V′2‚j=1‚2‚⋯‚m用类似于定理1(ⅰ)的证明方法,证得对任意正整数m,n,k,图Km,n是k-优美图.(ⅱ)设V2=V2(Gk-1),E2=E2(Gk-1),再设V=V(〈Km,n,Gk-1〉)=V1∪V2,E=