可滿著色圖的一種結(jié)構(gòu)

趙小玲

(上海電機(jī)學(xué)院 文理學(xué)院, 上海 201306)

對(duì)于可滿著色圖，呂長(zhǎng)虹等[7]進(jìn)行了一些深入研究，證明了以下的結(jié)論。

1 理論基礎(chǔ)

對(duì)于一般圖的廣義Mycielski圖，首先給出如下定義：

定義1G=(V,E)是一個(gè)簡(jiǎn)單圖，|G|=n,V(G)={v01,v02,…,v0n}，p≥2為給定的整數(shù)，Mp(G)稱為圖G廣義Mycielski圖，如果滿足:

V(Mp(G))={v01,v02,…,v0n,v11,v12,…,

v1n,…,vp1,vp2,…,vpn}

E(Mp(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),

1≤j,k≤n,i=0,1,…,p-1}

下面討論一般圖的廣義Mycielski圖的連續(xù)標(biāo)號(hào)問(wèn)題。下述定理可以說(shuō)明連續(xù)標(biāo)號(hào)的性質(zhì)。

引理3[3]對(duì)于任意n階的圖G，下列命題是等價(jià)的:

(1)圖G具有連續(xù)標(biāo)號(hào)。

(2)G的補(bǔ)圖中具有Hamilton路。

引理4[7]令Mp(Kn)是Kn的廣義Mycielski圖，則

2 主要結(jié)論

定理1對(duì)于任意的圖G，Mp(G)一定具有連續(xù)標(biāo)號(hào)。

由廣義Mycielski圖的定義，可以得到廣義Mycielski圖Mp(G)的補(bǔ)圖Mp(G)C的結(jié)構(gòu):

結(jié)論1令A(yù)i={vi1,vi2,…,vin}(i=0,1,…,p)，則A0的生成子圖是GC，其他Ai(i=1,2,…,p)的生成子圖都是完全圖Kn。

結(jié)論2vijv(i+1)j∈E(Mp(G)C),(i=0,1,…,p-1;j=1,2,…,n)。

結(jié)論3若v0jv0k∈E(Mp(G)C)，則

vijv(i+1)k∈E(Mp(G)C)，

(i=0,1,…,p-1;1≤j,k≤n)

由此，得到定理1的證明:

情況1當(dāng)GC中有一條Hamilton路，不妨設(shè)為v01v02…v0n。則可以用如下方法找到Mp(G)C的一條Hamilton路:

(1)當(dāng)p為偶數(shù)時(shí)，這條Hamilton路為

v01v02…v0n→v1nv1(n-1)…v11→

v21v22…v2n→……→vp1vp2…vpn

(2)當(dāng)p為奇數(shù)時(shí)，這條Hamilton路為

v01v02…v0n→v1nv1(n-1)…v11→

v21v22…v2n→……→vpnvp(n-1)…vp1

情況2當(dāng)GC的路覆蓋數(shù)為r(r≥2)，這r條路分別為P1,P2,…,Pr，設(shè)P1為v01v02…v0n1，P2為v0(n1+1)v0(n1+2)…v0(n1+n2)，…，

Pr為v0(n1+n2+…+nr-1+1)v0(n1+n2+…+nr-1+2)…

v0(n1+n2+…+nr-1+nr)。其中

n1+n2+…+nr-1+nr=n

則可以用如下方法找到Mp(G)C的一條Hamilton路:

v0n1v0(n1-1)…v01→v11v12…v1n1v1(n1+1)

→v0(n1+1)v0(n1+2)…v0(n1+n2)→v1(n1+n2)v1(n1+n2+1)

→v0(n1+n2+1)v0(n1+n2+2)…v0(n1+n2+n3)→…

→v0(n1+n2+…+nr-1+1)v0(n1+n2+…+nr-1+2)…

v0(n1+n2+…+nr-1+nr)v1(n1+n2+…+nr-1+nr)

→v2(n1+n2+…+nr-1+nr)v2(n1+n2+…+nr-1+nr-1)…v22v21

→v31v32…v3(n1+n2+…+nr-1+nr-1)v3(n1+n2+…+nr-1+nr)

→v4(n1+n2+…+nr-1+nr)v4(n1+n2+…+nr-1+nr-1)…v42v41

→…

(當(dāng)p為奇數(shù)時(shí))→vp1vp2…

vp(n1+n2+…+nr-1+nr-1)vp(n1+n2+…+nr-1+nr)。

(當(dāng)p為偶數(shù)時(shí))→vp(n1+n2+…+nr-1+nr)

vp(n1+n2+…+nr-1+nr-1)…vp2vp1。

對(duì)任意圖G，沿著Mp(G)C的該Hamilton路的軌跡進(jìn)行標(biāo)號(hào)，由引理3，Mp(G)一定有一個(gè)連續(xù)的L(2,1)標(biāo)號(hào)。

證畢。

由廣義Mycielski圖的定義，可得到廣義Mycielski圖Mp(G)的如下一些結(jié)構(gòu)特征:

結(jié)論4令A(yù)i={vi1,vi2,…,vin}(i=0,1,…,p)，則A0的生成子圖是G，其他Ai(i=1,2,…,p)的生成子圖都是獨(dú)立集。

結(jié)論5dMp(G)(vijv(i+1)j)≥3,(i=1,…,p-1;j=1,2,…,n)，dMp(G)(vijv(i+m)j)≥m,(i=0,1,…,p-m;j=1,2,…,n;m≥2)。

定理2的證明當(dāng)p=2時(shí)，觀察圖G的二串廣義Mycielski圖M2(G)。假設(shè)圖G的頂點(diǎn)集為A0，M2(G)的第1串和第2串的頂點(diǎn)集分別為A1、A2，顯然，A0的生成子圖即為G。記A0∪A1的生成子圖為G′，A0∪A1∪A2的生成子圖為G″。

當(dāng)p≥3時(shí)，由結(jié)論5

dMp(G)(vijv(i+3)j)≥3

(i=0,1,…,p-3;j,k=1,2,…,n)

證畢。