一些卡方積圖的符號星控制數(shù)

丁宗鵬，徐保根，張亞瓊

(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西 南昌，330013)

1 引言及定義

本次研究所考察的圖均為無向簡單圖，文中未說明的符號和術(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邊。

2 主要結(jié)果及其證明

定理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邊，這不滿足符號星控制的定義，矛盾)。……