徐保根，張君霞，李 廣

(華東交通大學(xué) 理學(xué)院，江西 南昌 330013)

0 引言

圖的控制理論是圖論中的重要內(nèi)容，其研究內(nèi)容越來越豐富，應(yīng)用越來越廣泛。本文中所指的圖均為無向簡單圖,符號和術(shù)語同文獻[1-2]。文獻[3]綜述了圖的控制理論方面的主要研究成果，但絕大多數(shù)屬于圖的點控制[4-5]，很少涉及到圖的邊控制及全控制問題。近些年來，隨著計算機技術(shù)的快速發(fā)展，圖的標(biāo)號理論得到了廣泛應(yīng)用，產(chǎn)生了圖的控制函數(shù)概念[6]，從而引出了許多新的控制概念，如符號全控制[7-8]、符號圈控制[9]、F-控制[10-11]和符號邊控制[12]等，極大地豐富和完善了圖的控制理論內(nèi)容，文獻[2]已綜述了近年來的研究成果。文獻[13]首次提出并研究了圖的符號控制概念，但確定這類控制參數(shù)是十分困難的，即使對于一些特殊的圖類，確定其符號控制數(shù)的確切值仍然很困難，本文研究并確定了兩類乘積圖的符號控制數(shù)。

1 定義

設(shè)G=(V,E)是一個圖，V(G)和E(G)分別為G的頂點集和邊集。N(v)為v點的鄰域，N[v]=N(v)∪{v}為v點的閉鄰域，d(v)=|N(v)|為v點的度，△=△(G)和δ=δ(G)分別為圖G的最大度和最小度。

定義1[1-2]設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個不交的圖，則G1與G2的笛卡爾(Cartesian)積圖(或稱為乘積圖)G1×G2定義為：

V(G1×G2)=V1×V2,E(G1×G2)={(u1,v1)(u2,v2)|u1=u2且v1～v2或者v1=v2且u1～u2}。

定義2[13]設(shè)G=(V,E)是一個圖，一個雙值函數(shù)f:V→{-1,+1}，如果對任意v∈V，均有f(N[v])≥1成立，則稱f為圖G的一個符號控制函數(shù)，圖G的符號控制數(shù)定義為γs(G)=min {f(V)|f為圖G的一個符號控制函數(shù)}。并稱滿足γs(G)=f(V)的符號控制函數(shù)f為圖G的一個最小符號控制函數(shù)。

一般來說，確定一個圖的符號控制數(shù)是困難的，對于乘積圖Pn×Pm和Cn×Pm，當(dāng)m=2時，文獻[14]中給出了Pn×P2和Cn×P2的符號控制數(shù)：

而當(dāng)m=3時，文獻[15]中也給出了Pn×P3的符號控制數(shù)，但其結(jié)論與本文結(jié)論不一致。

圖1 C9×P3的符號控制函數(shù)

對于Cn×P3，本文獲得了其符號控制函數(shù)，例如，當(dāng)n=9時，C9×P3的符號控制函數(shù)見圖1。不難驗證，γs(C9×P3)≤13，其標(biāo)號如圖1所示(未標(biāo)出的點均標(biāo)號為+1)。

這一結(jié)論是不正確的。例如，當(dāng)n=12時，按引理2則有γs(P12×P3)=20。

P12×P3的符號控制函數(shù)見圖2。但圖2顯示γs(P12×P3)≤18，其標(biāo)號如圖2所示(未標(biāo)出的點均標(biāo)號為+1)。

本文將給出Pn×P3和Cn×P3的符號控制數(shù)的正確結(jié)果，首先用到引理3：

引理3γs(P5×P3)=7，并且對于圖G=Pn×P3(n≥5)的任意一個符號控制函數(shù)f，在f下圖G=Pn×P3的一端(3行5列)中標(biāo)號為-1的點至多有4個。

引理3可以直接驗證。事實上，P5×P3的一個最小符號控制函數(shù)(標(biāo)號)f如圖3所示(未標(biāo)出的點均標(biāo)號為+1)。

圖2P12×P3的符號控制函數(shù)

圖3P5×P3的符號控制函數(shù)

2 主要結(jié)論及證明

證明記G=Cn×P3，其頂點集V(G)=V1∪V2∪V3，在G中，令：

V1={u1,u2,…,un}，V2={v1,v2,…,vn}，V3={w1,w2,…,wn}；

E(G)={uivi,viwi|1≤i≤n}∪{uiui+1,vivi+1,wiwi+1|1≤i≤n}；

un+1=u1，vn+1=v1，wn+1=w1。

首先證明：

(1)

令f為圖G的一個最小符號控制函數(shù)，即γs(G)=f(V)，記

A={v∈V(G)|f(v)=-1}，B={v∈V(G)|f(v)=+1}，

顯然V(G)=A∪B，并且γs(G)=|B|-|A|=n-2|A|。只需證明式(2)即可：

(2)

對于每個整數(shù)i=1,2,…,n，令A(yù)i={uj,uj,wj|i+1≤j≤i+5}，這時下標(biāo)取模n的最小正剩余。

另一方面，可以選取圖Cn×P3的頂點集的一個子集A如下，并由其定義符號控制函數(shù)。

不難驗證，f為圖G=Cn×P3的一個符號控制函數(shù)，因此有：

(3)

定理2設(shè)n≥3，則

(Ⅰ)γs(P3×P5)=7;

證明記G=P3×Pn，G為一個具有3行n列的格子圖，第1、2、3行的點集標(biāo)號見定理1。當(dāng)n=5時，由引理3可知定理2成立，下設(shè)n≠5。

定義圖G的一個函數(shù)g如下：

情況1若n=5k(k≠1)，令A(yù)={u2,w2,v4,v5,…,u5i+2,w5i+2,v5i+4,v5i+5,…,u5k-3,w5k-3,v5k-1}，則|A|=4k-1。

情況2若n=5k+1，令A(yù)={u2,w2,v4,v5,…,u5i+2,w5i+2,v5i+4,v5i+5,…,u5k-3,w5k-3,v5k-1,v5k}，則|A|=4k。

情況3若n=5k+2，令A(yù)={u2,w2,v4,v5,…,u5i+2,w5i+2,v5i+4,v5i+5,…,u5k-3,w5k-3,v5k-1,v5k,u5k+2}，則|A|=4k+1。

情況4若n=5k+3，令A(yù)={u2,w2,v4,v5,…,u5i+2,w5i+2,v5i+4,v5i+5,…,u5k-3,w5k-3,v5k-1,v5k,u5k+2,w5k+2}，則|A|=4k+2。

情況5若n=5k+4，令A(yù)={u2,w2,v4,v5,…,u5i+2,w5i+2,v5i+4,v5i+5,…,u5k-3,w5k-3,v5k-1,v5k,u5k+2,w5k+2,v5k+4}，則|A|=4k+3。

不難驗證,g是符號控制函數(shù)，從而有

(4)

設(shè)f為G的一個最小符號控制函數(shù)，即f(V(G))=γs(G)。令M={u∈V(G)|f(u)=-1}，|M|=m，P={u∈V(G)|f(u)=1}，|P|=t，可見m+t=3n。

對n用歸納法：