1. 引言
本文所指定的图均为无向简单图,文中未说明的符号和术语同文献 [1] 。设
是一个图,其顶点集
和边集
。对任意
,则
表示为u点在G中的领域,
为u点在G中的闭领域,
为u点在G中的度,而
和
分别为图G的最小度和最大度。在不致混淆情况下,可将
分别简单记为
。图G中两个顶点u和v之间的距离指连接这两个点的最短路的长度,记为
。
近几十年来,图的控制理论的研究内容越来越丰富,各种类型的符号控制数以及其变化的形式依次被提出,如图的符号控制数 [2] [3] [4] 、图的边符号控制数 [5] 、图的边全符号控制数 [5] 、图的符号全控制数 [6] [7] 、图的星符号控制数 [5] 、图的团符号(边)控制数 [5] 、图的逆符号(边)控制数 [5] 、图的反符号(边)控制数 [5] 、图的圈符号(边)控制数 [8] 、罗曼符号(边)控制数 [9] [10] 等。其中首次被提出的是图的符号控制概念,由J E Dunbar等人在1995年提出。图的符号控制数的研究有着广泛的应用背景,如交通岗位、物资供应点的设置等,但是符号控制数的计算是NP完全问题。
目前很多相关学者研究了关于图的符号全控制数的上下界 [11] [12] 以及特殊图的符号全控制数的精确值 [13] 。本文中主要得到了符号全控制数的一个下界以及两类图广义Petesen图
和Double广义Petesen图
的符号全控制数的精确值,这里
。
对于图
,定义一个函数
和G的一个子集
,记
。为简单起见,下文中适合
的顶点称为+1点,适合
的顶点称为-1点,用
表示模n的剩余类。
2. 基本概念
定义1 [6] :设图
为一个图,一个双值函数
,若
,则记
。
如果对任意的顶点
,均有
成立,则称f为图G的一个符号全控制函数,图G的符号全控制数定义为
并将使得
的符号全控制函数称f为图G的一个最小符号全控制函数。
从定义1可以看出以下性质。
性质:设G是
个顶点的简单图。若
是图G一个最小符号全控制函数,则有以下结论成立。
i)
ii)
定义2 [5] :设
都是正整数且
。广义Petersen图
是具有2n个顶点的图,它的顶点集
和边集
分别为:
定义3 [14] :设n和k是正整数且
。Double广义Petesen图
是4n个顶点的简单图,它的顶点集
和边集
分别为:
显然,广义Petersen图
和Double广义Petesen图
都是3-正则图。
引理 [6] :设G是一个r-正则图。若r是奇数,则
;若r是偶数,则
。
3. 主要定理及其证明
定理1:设图G是
个顶点的简单图。若
是图G一个最小符号全控制函数,且
,
,则有以下结论成立。
i)
;
ii)
;
iii)
;
证明:i) 假设
是图G一个最小符号全控制函数,由性质,有
从而有
ii) 由性质和i),推导出
通过移项,得
iii) 由性质和i),有
故,有
推论:设G是一个r-正则图,那么有
。
注:定理1的结果与引理的结论一致。
定理2:设图G是广义Petersen图
且
。那么
证明:令图G是广义Petersen图
,这里
。记
因此,有
由定理1,有
下面我们定义图G的一个符号全控制数f:
这里
容易验证,对于每个顶点
,有
。注意到此时图G中-1点个数t为
,+1点个数s为
。从而
因此,有
定理2:证毕。
定理3:设图G是Double广义Petesen图
且
。那么
证明:令图G是Double广义Petesen图
,这里
。记
因此,有
由定理1,有
下面我们定义图G的一个符号全控制数f:
这里
容易验证,对于每个顶点
,有
。注意到此时图G中-1点个数t为
,+1点个数s为
。从而
因此,有
定理3证毕。
基金项目
国家自然科学基金(No. 11701257, No.11801253, No. 11571005),河南省教育厅高校重点项目(No. 18A110025, No. 18A110026)、河南省科技计划项目(182102310930, 182102310955)、(2017-JSJYYB-074)。