王彩云， 李敏慧， 張淑敏,2

(1青海師范大學 數學與統(tǒng)計學院，青海 西寧 810008；2青海師范大學 高原科學與可持續(xù)發(fā)展研究院，青海 西寧 810008)

引言

本文所涉及的圖均為簡單的、連通的、有限的和無向的,未提及到的術語和符號可以參見文獻[1]。頂點v的開鄰域記為N(v),其中N(v)={u|uv∈E(G)}。圖G中一個頂點v的度,記為deg(v),定義為deg(v)=|N(v)|。若deg(v)=1,則頂點v稱為葉子。與葉子相鄰的頂點稱為支撐點，與葉子相關聯(lián)的邊稱為懸掛邊。

對于n,m≥3,雙星圖是通過把兩個不相交的星圖K1,n和K1,m連接中心點得到的一個圖,記為Sn,m設G和H是兩個簡單圖,G和H的鄰域皇冠圖G*H是由一個G和|V(G)|個圖H通過連接G的第i(1≤i≤|V(G)|)個頂點和H的第i(1≤i≤|V(H)|)個拷貝中的每個頂點構成的圖。圖G和H的聯(lián)圖G∨H是由G的每個頂點與H的所有頂點相連得到的圖。

一個圖G的Middle圖,記為M*(G)。圖M*(G)的頂點集是V(G)∪E(G),M*(G)中的兩個頂點x和y相鄰當且僅當

(1)x∈V(G),y∈E(G)并且x,y在G中是關聯(lián)的。

(2)x,y∈E(G)并且x,y在G中是相鄰邊。

當G是P4時,如圖1所示。

圖1 M*(P4)Fig.1 M*(P4)

一個圖G的Total圖,記為T(G)。圖T(G)的頂點集是V(G)∪E(G),T(G)中的兩個頂點x和y相鄰當且僅當

(1)x,y∈V(G)并且x,y在G中相鄰。

(2)x,y∈E(G)并且x,y在G中是相鄰邊。

x∈V(G),y∈E(G)并且x,y在G中是關聯(lián)的。

當G是P4時,如圖2所示。

圖2 T(P4)Fig.2 T(P4)

引理1.2[2]設G是一個連通圖,則

并且界是緊的。

引理1.4[10]設G是一個n階連通圖且n≥2,若圖G包含長為t的最長路,則

1 完全多部圖,風車圖等圖的全控制色數

本節(jié)得到幾類圖的全控制色數。根據引理1.2和χ(Kn1,n2,…,nk)=k可得命題2.1

證明：令完全k-部圖Kn1,n2,…,nk的頂點集為V(Kn1,n2,…,nk)=V1∪V2∪…∪Vk,其中|Vi|=ni(1≤i≤k)

圖的一個全控制染色Fig.3 A total dominator coloring of

證明：令參數m不變,并對參數n歸納。

下面,計算兩個簡單圖G和H的連圖G∨H的全控制色數。

定理2.4設G和H是兩個連通圖,則

證明：用顏色1,2,…,|V(G)|對圖G的頂點進行染色并且用顏色|V(G)|+1,|V(G)|+2,…,|V(G)|+χ(H)對圖H的頂點進行染色。根據全控制染色的定義,這種染色是圖G∨H的一個全控制染色。

類似的,用顏色1,2,…,|V(H)|對圖H的頂點進行染色并且用顏色|V(H)|+1,|V(H)|+2,…,|V(H)|+χ(G)對圖G的頂點進行染色。根據全控制染色的定義,這種染色是圖G∨H的一個控制染色。

2 Middle圖和Total圖的全控制色數

Kazemi在文獻[10]中計算了圖G的Central圖C(G)的全控制色數的上下界,那么,本節(jié)得出了圖G的Middle圖M*(G)的全控制色數:

設圖G的頂點集是V={v1,v2,…,vn},則V(M*(G))=V∪C其中C={cij|vivj∈E(G),i≠j∈1,2,…,n}。

情形1:t為偶數。

令

情形2t為奇數。

令

當G含哈密頓路時,由定理2.5可得出下面的推論:

推論2.6設G是一個n階連通圖且n≥3若G包含哈密頓路,則

證明：首先證明必要性。

假設G是n≥3個頂點的非完全圖且V(G)={v1,v2,…,vn}。不失一般性,設v1vn?E(G)。則V(M*(G))=V∪C其中C={cij|vivj∈E(G),i≠j∈1,2,…,n}。

其次證明充分性。

例2圖M*(K5)的一個全控制染色方案。

M*(K5)的一個全控制染色中的所有色類:

V1={c12},V2={c13},V3={c14},V4={c15},V5={c23},V6={c24},V7={c25},V8={c34},V9={c35},V10={c45},V11={v1,v2,v3,v4,v5}。

令V1={v1,v2,…,vn},Vi+1={c(i+1)t},1≤i≤n-1,則f=(V1,V2,…,Vn+1)是M*(Cn)的一個全控制染色。

由定理2.8可得下面的推論:

不失一般性,l=n+m+1意味著u0∈Vi,那么c00?tVi+1,因此有l(wèi)>n+m+2。

因為圖G的Middle圖M*(G)的連邊方式與圖G的Total圖T(G)的連邊方式相似,所以,通過上述的定理,分別得到完全圖Kn和雙星圖Sn,m的Total圖T(Kn)和T(Sn,m)的全控制色數。

設雙星圖Sn,m的頂點集為V(Sn,m)={v0,v1,v2,…,vm,u0,u1,u2,…,un}且邊集E(Sn,m)={u0v0,v0vj,u0ui}(1≤i≤n,1≤j≤m)。因此,T(Sn,m)的頂點集是V(T(Sn,m))=V∪C,其中C={c00,c0i,c0j|1≤i≤n,1≤j≤m}。

不失一般性,l=n+m+2意味著u0∈Vi,那么c00?tVi+1,因此有l(wèi)>n+m+2。不失一般性,l=n+m+3意味著u0∈Vi,那么c00?tVi+1,則l≥n+m+3。

當1≤i≤n,1≤j≤m時,令V1={ui,uj},Vi+1={c0i},Vi+j+1={cj0},Vn+m+2={c00},Vn+m+3={v0,u0i},則f=(V1,V2,…,Vn+m+3)是T(Sn,m)一個全控制染色。

上述定理的結論適用于連通圖,若圖G不連通,由定理2.5可得出定理2.14。

定理2.14設G是n階不連通圖且n≥2。若圖G由m個連通圖G1,G2,…,Gm組成,且每個連通圖Gi(1≤i≤m)包含長為t的最長路,則