關于圖的符號圈控制數

徐保根，鄒 妍，趙麗鑫

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

關于圖的符號圈控制數

徐保根，鄒 妍，趙麗鑫

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

設G＝（V，E）是一個圖，已有文獻提出了圖G的符號圈控制概念，本文研究了幾類積圖的符號圈控制問題，主要確定了積圖Pn×P2、Pn×P3和Cn×P2符號圈控制數，并給出了Pm×Pn的符號圈控制數的一個下界。

圖；符號控制；符號圈控制函數；符號圈控制數

0 引言

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

本文中所指的圖均為無向簡單圖，符號和術語同文獻［10］。

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

設G＝（V，E）為一個圖，f：E→R為一個實值函數，S?E，則記。文獻［1］中首先提出并研究了圖的符號圈控制。

定義1［1］設G＝（V，E）是一個圖，一個函數如果滿足f（E（C））≥1對G中每一個導出圈C均成立，則稱f為圖G的一個符號圈控制函數，圖G的符號圈控制數定義為為圖G的一個符號圈控制函數｝。

稱滿足γ′sc（G）＝f（E）符號圈控制函數f為G的一個最小符號圈控制函數。

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

一般地說，確定一個圖的符號圈控制數是非常困難的，文獻［9］中提出一個公開問題：確定積圖Pn×Pm的符號圈控制數這一問題目前還尚未解決。本文將確定積圖Pn×P2、Pn×P3和Cn×P2的符號圈控制數，并給出了Cm×Pn的符號圈控制數的一個下界。

1 主要結論及其證明

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

定理4 設整數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］ 徐保根，孔祥陽.圖的反減邊全控制［J］.河南科技大學學報：自然科學版，2011（4）：71－73.

［6］ 徐保根，張亞瓊，湯友亮.關于圖的符號邊控制數的一些結論［J］.河南科技大學學報：自然科學版，2012（4）：74－78.

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

［8］ 徐保根.關于圖的團符號控制數［J］.系統科學與數學，2008（3）：282－287.

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

［10］ Bondy JA，M ruty U SR.圖論及其應用［M］.吳望名，譯.北京：科學技術出版社，1984.

O157.5

A

1672－6871（2014）06－0080－04

國家自然科學基金項目（11361024）；江西省自然科學基金項目（20114BAB201010）；江西省高校科技落地計劃基金項目（KJLD12067）

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

2014－05－19