可滿著色圖的一種結構

趙小玲

(上海電機學院 文理學院, 上海 201306)

對于可滿著色圖，呂長虹等[7]進行了一些深入研究，證明了以下的結論。

1 理論基礎

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

定義1G=(V,E)是一個簡單圖，|G|=n,V(G)={v01,v02,…,v0n}，p≥2為給定的整數，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圖的連續標號問題。下述定理可以說明連續標號的性質。

引理3[3]對于任意n階的圖G，下列命題是等價的:

(1)圖G具有連續標號。

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

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

2 主要結論

定理1對于任意的圖G，Mp(G)一定具有連續標號。

由廣義Mycielski圖的定義，可以得到廣義Mycielski圖Mp(G)的補圖Mp(G)C的結構:

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

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

結論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當GC中有一條Hamilton路，不妨設為v01v02…v0n。則可以用如下方法找到Mp(G)C的一條Hamilton路:

(1)當p為偶數時，這條Hamilton路為

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

v21v22…v2n→……→vp1vp2…vpn

(2)當p為奇數時，這條Hamilton路為

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

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

情況2當GC的路覆蓋數為r(r≥2)，這r條路分別為P1,P2,…,Pr，設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

→…

(當p為奇數時)→vp1vp2…

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

(當p為偶數時)→vp(n1+n2+…+nr-1+nr)

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

對任意圖G，沿著Mp(G)C的該Hamilton路的軌跡進行標號，由引理3，Mp(G)一定有一個連續的L(2,1)標號。

證畢。

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

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

結論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的證明當p=2時，觀察圖G的二串廣義Mycielski圖M2(G)。假設圖G的頂點集為A0，M2(G)的第1串和第2串的頂點集分別為A1、A2，顯然，A0的生成子圖即為G。記A0∪A1的生成子圖為G′，A0∪A1∪A2的生成子圖為G″。

當p≥3時，由結論5

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

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

證畢。