关于图的符号圈控制数

徐保根，邹 妍，赵丽鑫

（华东交通大学理学院，江西 南昌 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