一些卡方積圖的符號星控制數

丁宗鵬，徐保根，張亞瓊

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

1 引言及定義

本次研究所考察的圖均為無向簡單圖，文中未說明的符號和術語均與文獻［1］相同。

近幾年來，圖的控制理論的研究內容越來越豐富。加拿大著名圖論專家COCKAYNE E J等先后引入了圖的許多不同類型的控制概念及其變化形式后，圖的控制理論出現了大量的研究成果。然而絕大多數是屬于圖的點控制，邊控制的研究成果還相對較少。在文獻［7］中徐保根定義了圖的符號邊控制概念，并獲得了較多的研究成果，隨后又從圖的符號邊控制拓展到了符號星控制上，并得出了一系列的研究成果。筆者在已有成果的基礎上又確定了幾類特殊圖的符號星控制數。

設一個圖G=(V，E)，v∈V，則v點在G中的邊鄰域定義為E(v)={uv∈E∣u∈V}。

定義 設G=(V，E)是一個沒有孤立頂點的圖，如果一個函數f:E→{+1，－1}，對一切v∈V(G)滿足)≥1成立，則稱f為圖G的一個符號星控制函數。圖G的符號星控制數定義為γ'ss(G)=minf為G的符號星控制函數}。

為了方便，如果f為G的一個符號星控制函數，則稱滿足f(e)=1的邊e是在f下的1邊;同樣稱滿足f(e)=－1的邊e是在f下的－1邊。

2 主要結果及其證明

定理1 對于圖G=Pm×Pn，當m，n為奇數且均大于1時，γ'ss(Pm×Pn)=mn－m－n+7。當m，n不全為奇數且均大于1時，γ'ss(Pm×Pn)=mn－m－n+4。

證明 情形1 當m，n全為奇數且均大于1時，對于圖G中其度數d(v)=2的點所關聯的邊均標號1。對于圖G中其度數d(v)=3或4的點(共(mn－4)個)，依據符號星控制的定義，每個點至多鄰接1條－1邊，從而圖G中至多有(－1)條－1邊(如果圖G中至少有即為條邊標號－1，那么至少存在一個點鄰接了2條－1邊，這不滿足符號星控制的定義，矛盾)。從而有

另一方面，給出圖G的一個標號，步驟如下:

將圖G=Pm×Pn畫在平面上，使其成m行n列的格圖。

(1)對圖G中其度數d(v)=2的點所關聯的邊均標號1(共8條)。

(2)對第一行和最后一行余下的所有行邊以－1，1依次交錯標號。

(3)對第二行到倒數第二行的所有奇數行邊標號－1。

(4)對最后一列余下的所有列邊以－1，1依次交錯標號。

(5)對圖G剩下的所有邊均標號1。

不難驗證此標號符合符號星控制的定義。于是有

綜上，當m，n全為奇數時，γ'ss(Pm×Pn)=mn－m－n+7。

情形2 當m，n不全為奇數均大于1時，不妨設n為偶數。對于圖G中其度數d(v)=2的點所關聯的邊均標號1，對于圖G中其度數d(v)=3或4的點(共(mn－4)個)，依據符號星控制的定義，每個點至多鄰接1條－1邊，從而圖G中至多有(mn－4)/2條－1邊。

從而有γ'ss(Pm×Pn)≥(m－1)n+m(n－1)－2·(mn－4)/2=mn－m－n+4。

另一方面，給出圖G的一個標號，步驟如下:

將圖G=Pm×Pn畫在平面上，使其成m行n列的格圖。

(1)對圖G中其度數d(v)=2的點所關聯的邊均標號1(共8條)。

(2)對第一行和最后一行余下的所有行邊以－1，1依次交錯標號。

(3)對第二行到倒數第二行的所有奇數行邊標號－1。

(4)對圖G剩下的所有邊均標號1。

不難驗證此標號符合符號星控制的定義。于是有

綜上，當m，n不全為奇數時，γ'ss(Pm×Pn)=mn－m－n+4。證畢。

定理2 對于圖G=Pm×Cn，當n為偶數時，γ'ss(Pm×Cn)=mn－n。

當n為奇數，m為偶數時，γ'ss(Pm×Cn)=mn－n。

當n為奇數，m為奇數時，γ'ss(Pm×Cn)=mn－n+1。

證明 情形1 當n為偶數時，對于圖G中其度數d(v)=3或4的點(共mn個)，依據符號星控制的定義，每個點至多鄰接1條－1邊，從而圖G中至多有(mn/2)條－1邊。

從而有 γ'ss(Pm×Cn)≥(m－1)n+mn－2·mn/2=mn－n。

另一方面，給出圖G的一個標號，步驟如下:

將圖G=Pm×Cn畫在平面上，使其成m個圈n條柱的圖。

(1)對圖G中的m個圈，對應取出每個圈上的最大獨立邊集(條)標號－1。

(2)對圖G中剩下的所有邊均標號1。

不難驗證此標號符合符號星控制的定義。于是有

綜上，當n為偶數時，γ'ss(Pm×Cn)=mn－n。

情形2 當n為奇數，m為偶數時，對于圖G中其度數d(v)=3或4的點(共mn個)，依據符號星控制的定義，每個點至多鄰接1條－1邊，從而圖G中至多有(mn/2)條－1邊。

從而有 γ'ss(Pm×Cn)≥(m－1)n+mn－2·mn/2=mn－n。

另一方面，給出圖G的一個標號，步驟如下:

將圖G=Pm×Cn畫在平面上，使其成m個圈n條柱的圖。

(1)對圖G中的m個圈，對應取出每個圈上的最大獨立邊集(條)標號－1。

(2)在所有鄰邊均未標號的一條柱上，取出其最大獨立邊集(條)標號－1。

(3)對圖G中剩下的所有邊均標號1。

不難驗證此標號符合符號星控制的定義。于是有

綜上，當n為奇數，m為偶數時，γ'ss(Pm×Cn)=mn－n。

情形3 當n為奇數，m為奇數時，對于圖G中其度數d(v)=3或4的點(共mn個)，依據符號星控制的定義，每個點至多鄰接1條－1邊，從而圖G中至多有「」條－1邊。

另一方面，給出圖G的一個標號，步驟如下:

將圖G=Pm×Cn畫在平面上，使其成m個圈n條柱的圖。

(1)對圖G中的m個圈，對應取出每個圈上的最大獨立邊集(條)標號－1。

(3)對圖G中剩下的所有邊均標號1。

不難驗證此標號符合符號星控制的定義。于是有

綜上，當n為奇數，m為奇數時，γ'ss(Pm×Cn)=mn－n+1。證畢。

［1］ 徐保根.圖的控制理論［M］.北京:科學出版社，2008.

［2］ BONDY JA，MURTY V SR.Graph theory with applications［M］.New York:Elsevier，1976.

［3］ HAYNESTW，HEDETNIEMIST，SLATER P J.Domination in graphs［M］.New York:Marcel Dekker INC，1998.

［4］ F·哈拉里.圖論［M］.上海:上海科學技術出版社，1980.

［5］ XU Bao－gen.On minus domination and signed domination in graphs［J］.Journal of Mathematical Research ＆ Exposition，2003，23(4):585－590.

［6］ 徐保根.兩類圖的符號星控制數［J］.華東交通大學學報，2005，22(4):146－148.

［7］ XU Bao－gen.On signed edge domination of graphs［J］.Journal of Mathematical Research and Exposition，2007，27(1):7－12.

［8］ 徐保根，李春華.圖的符號星k控制數［J］.純粹數學與應用數學，2009，25(4):638－641.

［9］ XU Bao－gen.On signed cycle domination in graphs［J］.Discrete Math，2009(4):309:1 007－1 012.

［10］ 黃中升，邢化明，趙燕冰.圖的逆符號邊控制數的上界［J］.應用數學學報，2010，33(5):840－846.