關(guān)于圖的符號(hào)圈控制數(shù)

徐保根，鄒 妍，趙麗鑫

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

關(guān)于圖的符號(hào)圈控制數(shù)

徐保根，鄒 妍，趙麗鑫

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

設(shè)G＝（V，E）是一個(gè)圖，已有文獻(xiàn)提出了圖G的符號(hào)圈控制概念，本文研究了幾類(lèi)積圖的符號(hào)圈控制問(wèn)題，主要確定了積圖Pn×P2、Pn×P3和Cn×P2符號(hào)圈控制數(shù)，并給出了Pm×Pn的符號(hào)圈控制數(shù)的一個(gè)下界。

圖；符號(hào)控制；符號(hào)圈控制函數(shù)；符號(hào)圈控制數(shù)

0 引言

圖的控制理論是圖論中的重要內(nèi)容［1］，近年來(lái)，其研究?jī)?nèi)容越來(lái)越廣泛，文獻(xiàn)［2］綜述了近40年來(lái)圖的控制理論研究方面的主要研究成果，但均屬于圖的點(diǎn)控制問(wèn)題。文獻(xiàn)［3］首先提出并研究了圖的符號(hào)邊控制，由此多種邊上的符號(hào)控制概念，如符號(hào)星控制［4］、反減邊全控制［5］、符號(hào)邊控制［6］、圈符號(hào)控制［7］、符號(hào)團(tuán)控制［8］等，從而使得控制理論的研究?jī)?nèi)容和研究成果越來(lái)越豐富，文獻(xiàn)［9］綜述了這些方面的研究成果。

本文中所指的圖均為無(wú)向簡(jiǎn)單圖，符號(hào)和術(shù)語(yǔ)同文獻(xiàn)［10］。

設(shè)G＝（V，E）是一個(gè)圖，若C為圖G中的一個(gè)圈，若V（C）在G中的導(dǎo)出子圖G［V（C）］＝C，則稱C為圖G的一個(gè)導(dǎo)出圈或無(wú)弦圈。用Cn和Pn分別表示n階圈和路。

設(shè)G＝（V，E）為一個(gè)圖，f：E→R為一個(gè)實(shí)值函數(shù)，S?E，則記。文獻(xiàn)［1］中首先提出并研究了圖的符號(hào)圈控制。

定義1［1］設(shè)G＝（V，E）是一個(gè)圖，一個(gè)函數(shù)如果滿足f（E（C））≥1對(duì)G中每一個(gè)導(dǎo)出圈C均成立，則稱f為圖G的一個(gè)符號(hào)圈控制函數(shù)，圖G的符號(hào)圈控制數(shù)定義為為圖G的一個(gè)符號(hào)圈控制函數(shù)｝。

稱滿足γ′sc（G）＝f（E）符號(hào)圈控制函數(shù)f為G的一個(gè)最小符號(hào)圈控制函數(shù)。

定義2［10］設(shè)G＝（V1，E1）和H＝（V2，E2）為兩個(gè)不交的圖，積圖G×H定義如下：

一般地說(shuō)，確定一個(gè)圖的符號(hào)圈控制數(shù)是非常困難的，文獻(xiàn)［9］中提出一個(gè)公開(kāi)問(wèn)題：確定積圖Pn×Pm的符號(hào)圈控制數(shù)這一問(wèn)題目前還尚未解決。本文將確定積圖Pn×P2、Pn×P3和Cn×P2的符號(hào)圈控制數(shù)，并給出了Cm×Pn的符號(hào)圈控制數(shù)的一個(gè)下界。

1 主要結(jié)論及其證明

定理1 對(duì)于任意整數(shù)n≥2，則有γ′sc（Pn×P2）＝n。的證明方法，可以得出其一個(gè)類(lèi)似于式（1）的下界。

定理4 設(shè)整數(shù)m≥n≥3，則有γ′sc（Pm×Pn）≥（m－1）（n－1）＋1。

［1］ Xu B G.On Signed Cycle Domination Numbers in Graphs［J］.Discrete Math，2009，309：1007－1012.

［2］ Haynes TW，Hedetniemi S T，Slater P J.Domination in Graphs［M］.New York：Marcel Dekker，Inc.，1998.

［3］ Xu B G.On Signed Edge Domination Numbers of Graphs［J］.Discrete Math，2001，239：179－189.

［4］ Xu B G.Two Classes of Edge Domination in Graphs［J］.Discrete Appl Math，2006，154：1541－1546.

［5］ 徐保根，孔祥陽(yáng).圖的反減邊全控制［J］.河南科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（4）：71－73.

［6］ 徐保根，張亞瓊，湯友亮.關(guān)于圖的符號(hào)邊控制數(shù)的一些結(jié)論［J］.河南科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（4）：74－78.

［7］ 徐保根，康洪波，趙利芬，等.圖的圈符號(hào)控制數(shù)［J］.中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2013（6）：136－138.

［8］ 徐保根.關(guān)于圖的團(tuán)符號(hào)控制數(shù)［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2008（3）：282－287.

［9］ 徐保根.圖的控制與染色理論［M］.武漢：華中科技大學(xué)出版社，2013.

［10］ Bondy JA，M ruty U SR.圖論及其應(yīng)用［M］.吳望名，譯.北京：科學(xué)技術(shù)出版社，1984.

O157.5

A

1672－6871（2014）06－0080－04

國(guó)家自然科學(xué)基金項(xiàng)目（11361024）；江西省自然科學(xué)基金項(xiàng)目（20114BAB201010）；江西省高?？萍悸涞赜?jì)劃基金項(xiàng)目（KJLD12067）

徐保根（1963－），男，江西南昌人，教授，主要從事圖論及應(yīng)用研究.

2014－05－19