關(guān)于k-優(yōu)優(yōu)觀的討論

關(guān)于k-優(yōu)優(yōu)觀的討論

在設(shè)計(jì)的美麗方面的研究中，許多結(jié)論都是基于連通性的，而對(duì)非連通性的研究結(jié)論很少（見(jiàn)文獻(xiàn)）。在這項(xiàng)工作中，我們研究了傾斜圖wn和完整圖km、圖1和k-1之間的非連通性圖的美麗關(guān)系，并證明了當(dāng)n為奇時(shí)，圖wngk-1是美麗的圖。當(dāng)n為偶，接圖wn和gk-1是美麗的圖，并證明接圖km、n和gk-1是美麗的圖。以下所討論的圖G(V,E)均為簡(jiǎn)單無(wú)向圖,設(shè)V=V(G)為圖G的頂點(diǎn)集,E=E(G)為圖G的邊集,|E|為圖G的邊數(shù),G1∨G2為圖G1與G2的聯(lián)圖,G1∪G2為圖G1與G2的并圖,ˉG為圖G的補(bǔ)圖,?Wn為齒輪圖,〈G1,G2〉為有根圖G1與G2兩根粘接而成的圖,Km,n為完全二部圖,Kn為n個(gè)頂點(diǎn)的完全圖,Pn為n個(gè)頂點(diǎn)的路,Cn為n個(gè)頂點(diǎn)的圈,Dm為m個(gè)K3恰有1個(gè)公共點(diǎn)的風(fēng)車(chē)圖.定義1設(shè)圖G=(V,E),k為正整數(shù),如果存在一個(gè)單射f:V→{0?1???|E|+k-1},使得對(duì)所有的邊uv∈E,由f′(uv)=|f(u)-f(v)|導(dǎo)出一個(gè)雙射f′:E→{k?k+1???|E|+k-1},則稱圖G是k-優(yōu)美圖,f是G的k-優(yōu)美標(biāo)號(hào).1-優(yōu)美圖也稱優(yōu)美圖,1-優(yōu)美標(biāo)號(hào)也稱優(yōu)美標(biāo)號(hào).定理1設(shè)n,k為任意正整數(shù),Gk-1是任意一個(gè)邊數(shù)為k-1的優(yōu)美圖,若n≥3,k≥n,則(ⅰ)圖?Wn是k-優(yōu)美圖;(ⅱ)當(dāng)n為奇數(shù)時(shí),圖?Wn∪Gk-1是優(yōu)美圖;(ⅲ)當(dāng)n為偶數(shù)時(shí),粘接圖〈?Wn,Gk-1〉是優(yōu)美圖.gxix1(ⅰ)設(shè)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當(dāng)n≡0(mod2)時(shí),定義圖?Wn的頂點(diǎn)標(biāo)號(hào)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下面證明標(biāo)號(hào)g是圖?Wn的k-優(yōu)美標(biāo)號(hào).由于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}是單射.對(duì)所有的邊uv∈E1,設(shè)g′(uv)=|g(u)-g(v)|.對(duì)于邊標(biāo)號(hào)g′分6部分考慮:①g′(x0x(1)i)=3n-i+k(i=1,2,…,n),當(dāng)i取遍1,2,…,n時(shí),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),當(dāng)i取遍1?2???n2時(shí),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),當(dāng)i取遍1?2???n2時(shí),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),當(dāng)i取遍n2+1?n2+2???n時(shí),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),當(dāng)i取遍n2+1?n2+2???n-1時(shí),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.設(shè)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}是雙射.則當(dāng)n≡0(mod2)時(shí),圖?Wn是k-優(yōu)美圖.情況2當(dāng)n≡1(mod2)時(shí),定義圖?Wn的頂點(diǎn)標(biāo)號(hào)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下面證明標(biāo)號(hào)g是圖W?n的k-優(yōu)美標(biāo)號(hào).由于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}是單射.對(duì)所有的邊uv∈E1,設(shè)g′(uv)=|g(u)-g(v)|.對(duì)于邊標(biāo)號(hào)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}是雙射.則當(dāng)n≡1(mod2)時(shí),圖W?n是k-優(yōu)美圖.綜上所述,對(duì)任意正整數(shù)n,k,當(dāng)n≥3,k≥n時(shí),W?n是k-優(yōu)美圖.(ⅱ)當(dāng)n為奇數(shù)時(shí),設(shè)V2=V2(Gk-1),E2=E2(Gk-1),有|E2|=k-1,h是優(yōu)美圖Gk-1的優(yōu)美標(biāo)號(hào),則映射h:V2(Gk-1)→{0?1?2???k-1}是單射,映射h′:E2(Gk-1)→{1?2?3???k-1}是雙射.設(shè)V=V(W?n∪Gk-1)=V1∪V2?E=(W?n∪Gk-1)=E1∪E2,有|E|=3n+k-1.下面分2種情形討論.情形1當(dāng)n,k同為奇數(shù)時(shí),定義圖W?n∪Gk-1的頂點(diǎn)標(biāo)號(hào)f為f(u)=g(u)u∈V1(1)f(v)=h(v)+2n-2v∈V2(2)下面證明標(biāo)號(hào)f是圖W?n∪Gk-1的優(yōu)美標(biāo)號(hào).由于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)).又因?yàn)閂1∩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}是雙射.當(dāng)uv∈E1時(shí),f′(uv)=|f(u)-f(v)|=|g(u)-g(v)|=g′(uv),則f′(E1)=g′(E1);當(dāng)uv∈E2時(shí),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(wàn)′(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}是雙射.則當(dāng)n,k同為奇數(shù)時(shí),W?n∪Gk-1是優(yōu)美圖.情形2當(dāng)n為奇數(shù)、k為偶數(shù)時(shí),定義圖W?n∪Gk-1的頂點(diǎn)標(biāo)號(hào)f為f(u)=g(u)u∈V1f(v)=h(v)+2n-1v∈V2同理證得:當(dāng)n為奇數(shù)、k為偶數(shù)時(shí),W?n∪Gk-1是優(yōu)美圖.綜上所述,n為奇數(shù)時(shí),W?n∪Gk-1是優(yōu)美圖.(ⅲ)設(shè)V=V(?W?n?Gk-1?)=V1∪V2?E=E(?W?n?Gk-1?)=E1∪E2,則|E|=3n+k-1.定義粘接圖〈W?n,Gk-1〉的頂點(diǎn)標(biāo)號(hào)f為f(u)=g(u)u∈V1(3)f(v)=h(v)+2nv∈V2(4)下面證明標(biāo)號(hào)f是粘接圖〈W?n,Gk-1〉的優(yōu)美標(biāo)號(hào).由于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)).又因?yàn)閒(V1)與f(V2)只有一個(gè)等值的頂點(diǎn),即優(yōu)美圖Gk-1中原始優(yōu)美標(biāo)號(hào)h(v)=0的頂點(diǎn)v在映射f的作用下有f(v)=f(xn(2)),把W?n和Gk-1中等值的頂點(diǎn)xn(2)和v當(dāng)作根,將兩根粘接在一起得到粘接圖〈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}是雙射.當(dāng)uv∈E1時(shí),f′(uv)=|f(u)-f(v)|=|g(u)-g(v)|=g′(uv),則f′(E1)=g′(E1);當(dāng)uv∈E2時(shí),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(wàn)′(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}是雙射.綜上所述,當(dāng)n為偶數(shù)時(shí),粘接圖〈W?n,Gk-1〉是優(yōu)美圖.例1(ⅰ)當(dāng)n=11,k=12時(shí),W?11∪(Ρ1∨Ρ6)是優(yōu)美圖,其優(yōu)美標(biāo)號(hào)如圖1所示.(ⅱ)當(dāng)n=8,k=22時(shí),W?8與P1∨P5的2-冠的粘接圖是優(yōu)美圖,其優(yōu)美標(biāo)號(hào)如圖2所示(實(shí)心點(diǎn)·為圖的根,將兩根粘接).定理2設(shè)m,n,k為任意正整數(shù),Gk-1是任意一個(gè)邊數(shù)為k—1的優(yōu)美圖.若k≥2,則(ⅰ)圖Km,n是k-優(yōu)美圖;(ⅱ)粘接圖〈Km,n,Gk-1〉是優(yōu)美圖.k-佳合圖的類型(ⅰ)設(shè)V1(Km,n)=V′1∪V′2,|V′1|=m,|V′2|=n,E1=E1(Km,n),|E1|=mn.定義圖Km,n的頂點(diǎn)標(biāo)號(hào)g為g(vi)=i-1vi∈V′1?i=1?2???mg(uj)=jm+k-1uj∈V′2?j=1?2???m用類似于定理1(ⅰ)的證明方法,證得對(duì)任意正整數(shù)m,n,k,圖Km,n是k-優(yōu)美圖.(ⅱ)設(shè)V2=V2(Gk-1),E2=E2(Gk-1),再設(shè)V=V(〈Km,n,Gk-1〉)=V1∪V2,E=