丁宗鵬,徐保根,張亞瓊
(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西 南昌,330013)
本次研究所考察的圖均為無向簡單圖,文中未說明的符號和術(shù)語均與文獻(xiàn)[1]相同。
近幾年來,圖的控制理論的研究內(nèi)容越來越豐富。加拿大著名圖論專家COCKAYNE E J等先后引入了圖的許多不同類型的控制概念及其變化形式后,圖的控制理論出現(xiàn)了大量的研究成果。然而絕大多數(shù)是屬于圖的點(diǎn)控制,邊控制的研究成果還相對較少。在文獻(xiàn)[7]中徐保根定義了圖的符號邊控制概念,并獲得了較多的研究成果,隨后又從圖的符號邊控制拓展到了符號星控制上,并得出了一系列的研究成果。筆者在已有成果的基礎(chǔ)上又確定了幾類特殊圖的符號星控制數(shù)。
設(shè)一個(gè)圖G=(V,E),v∈V,則v點(diǎn)在G中的邊鄰域定義為E(v)={uv∈E∣u∈V}。
定義 設(shè)G=(V,E)是一個(gè)沒有孤立頂點(diǎn)的圖,如果一個(gè)函數(shù)f:E→{+1,-1},對一切v∈V(G)滿足)≥1成立,則稱f為圖G的一個(gè)符號星控制函數(shù)。圖G的符號星控制數(shù)定義為γ'ss(G)=minf為G的符號星控制函數(shù)}。
為了方便,如果f為G的一個(gè)符號星控制函數(shù),則稱滿足f(e)=1的邊e是在f下的1邊;同樣稱滿足f(e)=-1的邊e是在f下的-1邊。
定理1 對于圖G=Pm×Pn,當(dāng)m,n為奇數(shù)且均大于1時(shí),γ'ss(Pm×Pn)=mn-m-n+7。當(dāng)m,n不全為奇數(shù)且均大于1時(shí),γ'ss(Pm×Pn)=mn-m-n+4。
證明 情形1 當(dāng)m,n全為奇數(shù)且均大于1時(shí),對于圖G中其度數(shù)d(v)=2的點(diǎn)所關(guān)聯(lián)的邊均標(biāo)號1。對于圖G中其度數(shù)d(v)=3或4的點(diǎn)(共(mn-4)個(gè)),依據(jù)符號星控制的定義,每個(gè)點(diǎn)至多鄰接1條-1邊,從而圖G中至多有(-1)條-1邊(如果圖G中至少有即為條邊標(biāo)號-1,那么至少存在一個(gè)點(diǎn)鄰接了2條-1邊,這不滿足符號星控制的定義,矛盾)。……