两类联图的符号控制数

张靖宇，红 霞

（洛阳师范学院数学科学学院，河南 洛阳 471022）

0 引言

本文所考虑的图均为简单图，且文中没有进行说明的图论中术语以及符号，见参考文献[1].

设G＝（V，E）是一个简单图，其顶点集为 V＝V（G）和边集为 E＝E（G）.对任意u∈V（G），则 NG（u）为 u点在G中的邻域，NG[u]＝NG（u）∪{u}为 u点在G中的闭邻域，为u点在G中的度，而δ＝δ（G）和Δ＝Δ（G）分别为图G的最小度和最大度.在不致混淆情况下，可将 NG（u），NG[u]，Δ（G）.δ（G）分别简单记为 N（u），N[u]，Δ，δ.用Kn，W1·n，分别表示n阶完全图、n＋1阶轮图和m阶完全图的补图.表示图的每个顶点与H的每个顶点相连接的联图.

图论的发展近几十年来非常迅速，特别是图的控制理论方向，其研究内容以及延伸的概念越来越多，诸多学者们依次提出有不同类型的控制数和相关的概念，比如首先提出的是图的顶点符号控制数[2]，是由J E Dunbar等人在1995年提出的.其次提出的是图的边（全）符号控制数[3]、延伸定义的概念有图的符号全控制数[4]以及图的圈符号（边）控制数[5].最近比较活跃的概念是罗曼符号（边）控制数[6-7]等.事实上，控制理论中研究符号控制数的应用背景与我们现实生活有着密切关系，如选择适合的交通岗位、选最优的物资供应点的设置等.

至今为止，很多学者也纷纷参与这项庞大研究领域并从中得到了有价值的研究成果.比如，已经确定有关于图的符号控制数的界[8].另外，文献[9]也确定了特殊图的符号控制数的精确值.文献[10]中，给出了两类特殊图气球图和哑铃图的符号控制数，这里所谓的气球图是指路Pm的一个端点与圈Cm中的一个顶点粘合（重合）而成的图.所谓哑铃图是指路Pm的两个端点分别粘接一个圈Cm而成的图.文献[11]中，作者高婷等人给出了Mycielski图（由路和圈构成）的符号圈控制数.文献[12]中，作者李宁等人计算出了两类笛卡尔乘积图（圈和路）的符号控制数.本文主要确定了两类联图的符号控制数的精确值.

对于图G＝（V，E），定义一个函数f:V→R和G的一个子集S⊆V（G），记f（S）＝∑v∈Sf（v）.

1 基本概念

定义1[2]设图G＝（V，E）为一个图，一个双值函数f:V→{1，－1}，如果对任意的顶点v∈V，均有f（N[v]）≥1成立，则称f为图G的一个符号控制函数.图G的符号控制数定义为是图G的一个符号控制函数}，并将使得γS（G）＝f（V）的符号控制函数称f为图G的一个最小符号控制函数.

2 主要结果