1. 引言
我们考虑的是有限的、简单的且连通的图。符号图是图的一类延伸,近几年来对符号图的研究是一个热点,例如,符号图流的问题 [1],符号图的最小圈覆盖问题 [2],符号图的同态问题 [3],符号图的染色问题 [4],符号图的圆盘染色问题 [5] 等等。符号图的概念最初由Harary [6] 在1953年提出。符号图
是指图G和定义在图G的边集上的映射
,其中
称为G的一个符号配置。如果
,记e是正边,否则e就是负边。
奇偶符号图是一种特殊的符号图。奇偶符号图的概念最初是由Acharya和Kureethara [7] 提出的。符号图
称作奇偶符号图,如果存在一个双射
,使得对于图G的每一条边
,若
,则
和
有相同的奇偶性;若
,则
和
有相反的奇偶性。这里的双射f称为图G (也称为S)的一个奇偶标记,
称为
的一个奇偶符号。Acharya、Kureethara和Zaslavsky [8] 刻画了奇偶符号图,其刻画如下:一个符号图S是一个奇偶符号图当且仅当S可以划分成两部分A和B,使得
,并且S的任意两个相邻的顶点u和v在一个集合中当且仅当边uv是正边。在本文中,这种划分
称作奇偶划分。奇偶符号图的这种刻画成立,其原因在于图G的一个奇偶标记可导出对应的一个奇偶划分:
Acharya和Kureethara [7] 定义了奇偶符号图的rna数。设G是一个图,
表示为符号图
在所有可能奇偶符号
下负边数的集合。图G的rna数定义为奇偶符号图
在所有可能的奇偶标记下负边数最小值,根据定义可以得到:
。
对于
,Harary图
的顶点集记为
,根据k和n的奇偶性,Harary图分为以下三种类型:
类型1:当k是偶数时,记
,两个顶点
和
相邻当且仅当
。
类型2:当k是奇数,n是偶数时,记
,则
由
通过添加边
得到。
类型3:当k是奇数,n是奇数时,记
,则
由
通过加边
得到。
实质上,Harary图
是将n个顶点等距离地排成一个环,并且根据k和n的奇偶性向环上加弦。为了方便起见,本文中所有顶点的下标都对模n同余。将Harary图
的外环记为
,由Harary图
的定义,对于第一、二种类型的Harary图
,
是k-正则的;对于第三种类型的Harary图
,除了一个顶点
的度是
,其余所有顶点的度均是k。当
时,
是一个环。因此,
。在本文中,我们只研究
的情况。首先我们计算了
,
,
的精确值,随后我们给出了三种类型的Harary图
的rna数的上下界:
。
本文用到其他一些数学符号,其定义如下。
,
,
分别表示图G的最小度,点连通度和边连通度,
表示边子集或顶点子集F在图G的导出子图,
中的顶点v的度记为
。设
是一个符号图,S的所有负边组成的集合记为
。令
和
是图G的两个不相交的点集,记
表示为连接
中的顶点到
中的顶点的边集,当G在上下文已经明确时,简写为
。
2. 主要结论及其证明
引理1
。
证明 对于Harary图
来说,有
,由rna数的定义知,
。
引理2 在
(
除外)的奇偶划分
下,边割集
的导出子图不可能是一个星。
证明 假设
的导出子图是一个星。不妨假设v是该星的中心且
。则对于
的任意一个圈C,若C含有B中的点,则
。特别地,记
的外环仅包含A中最多一个顶点,与Harary图的外环包含
的所有顶点这个事实矛盾。故假设不成立,即
的导出子图不可能是一个星。
引理3
在任意一个奇偶划分下,边割集长度不可能是3。
证明 对于
时,在任意一个奇偶划分下,
的边割集长度一定是偶数。对于
的情况,我们从Harary三种类型的图出发证明引理。假设存在一种奇偶划分
,其中
,
,使得
。
情形1 当
为Harary图的第一种类型时,此时k为偶数,由握手定理,
的值是偶数,则
的值一定是偶数,因此,边割集长度不可能是3。
情形2 当
为Harary图的第二种类型时。当
为偶数时,由握手定理,
的值是偶数,则
的值一定是偶数。因此,我们讨论当
为奇数时的情况。
情形2.1 当
时,易知
。设
,
,
。如果
,由引理2,则
,并且
,此时
,由假设
,则
,而此时
,与
矛盾,故有
,同理可得
,此时
,则有
,
,而此时
,与
矛盾。
情形2.2 当
时,根据引理1,
,所以
在奇偶划分下,边割集长度不可能是3。
情形3 当
为Harary图的第三种类型时。
情形3.1 当
时,易知
。不妨设
,
,
如果
,由引理2,则
,
,此时
,要满足条件
,则
,而此时
,与
矛盾,故
,同理
,此时
,则
,于是
,与假设矛盾,故
时,
在奇偶划分下,边割集长度不可能是3。
情形3.2 当
时,根据引理1,
,所以
在奇偶划分下,边割集长度不可能是3。
综上所述
在任意一个奇偶划分下,边割集长度不可能是3。
定理2
证明
只可能为Harary图的第二种类型和第三种类型,因此我们分为以下两种情形考虑。
情形1 当
为Harary图的第二种类型时。
情形1.1 当
为偶数时,由引理3,
,下面我们来证明
。我们给出一个Harary图的奇偶标记使得
恰好包括4条负边。设
定义如下:
由映射易知,f是一个奇偶标记,可导出对应的奇偶划分:
,
,
此时
,所以
。
情形1.2 当
为奇数时,设有奇偶划分
,由握手定理,
的值是一个偶数,则
的值一定是奇数,再结合引理3,
,下面我们来证明
。我们给出一个Harary图的奇偶标记使得
恰好包括5条负边。设
定义如下:
由映射易知,f是一个奇偶标记,可导出对应的一个奇偶划分:
,
。
因此,
,所以
。
情形2 当
为Harary图的第三种类型时,由引理3,
,下面我们来证明
。我们给出一个Harary图的奇偶标记使得
恰好包括4条负边。给定
一个奇偶划分
:
,
此时
,所以
。
引理4
在任意一个奇偶划分下,边割集长度不可能是4。
证明 假设
存在一种的奇偶划分
,其中
,
,使得
。
情形1
。不妨设
,
,
。因为
包含
的两条弦,则这两条弦的端点可分为如下四种子情况。
情形1.1 如果这两条弦的两个端点分别为
,
,假设
,
,此时
,则
,
,与
矛盾,故假设不成立。假设
,
,
,则
,与奇偶划分矛盾,故假设不成立。如果
,
,
,则
,
,此时
,与
矛盾,故情形1.1不存在。
情形1.2 如果这两条弦的共同的端点为
,
中其中一个顶点时,不妨设这个端点为
。根据引理2,
,此时
,与
包含
的两条弦矛盾。故情形1.2不存在。
情形1.3 如果
、
中只有一个顶点作为这两条弦的端点时,不妨设
为其中一条弦的端点并且
,则
,
,此时
,与假设矛盾。故情形1.3不存在。
情形1.4 如果
,
均不作为这两条弦的端点,则有
,
,此时
,与假设矛盾。故情形1.4不存在。
情形2
。不妨设
,
,
,易知
,则
,矛盾。
综上所述
在任意一个奇偶划分下,边割集长度不可能是4。
定理3
。
证明 假设
存在一种的奇偶划分
使得
,则
的值是偶数,则
的值一定是偶数,再结合引理4,
,下面我们来证明
。我们给出一个Harary图的奇偶标记使得
恰好包括6条负边。设
定义如下:
由映射易知,f是一个奇偶标记,我们可以写出相应的负边集合:
,
所以
。
定理4 对任意的正整数
,
。
证明 对于图
来说,设
定义如下:
由映射易知,f是一个奇偶标记,可导出对应的一个奇偶划分:
,
这里
,
均是两个完全图
,因此在这种奇偶划分下,边割集长度一定最小,因此,
。
定理5 对任意的正整数
,有
。
证明 设
环上的点依次为
。记
,
。则
为
的一种奇偶划分。容易看出,
,
分别是两个完全图
,
。因此,在这种奇偶划分下,边割集长度一定最小。因此,
。
Ligang Jin和Xiaoyue Chen [9] 给出了对于任意一个图G的rna数的上界:对于
个顶点,m条边的图G,
,当且仅当
或
或
时等式成立。现在将这个上界应用到Harary图上。
引理5 对于任意的
,有
。
证明 下界由引理1,
。上界代入公式
。对于第一、二种类型的Harary图来说,
,因此
;对于第三种类型的Harary图来说,
,因此
。
3. 总结与展望
本文研究了Harary图的rna数,我们通过分析Harary图的结构性质,计算出了一些特殊类型Harary图rna数的精确值,并且借助文献 [8] 中的结论给出了Harary图rna数的上下界。值得注意的是,从
,
,
的值可以看出,本文中给出Harary图rna数的下界不是紧的,这还需要我们继续加以改进。
基金项目
国家自然科学基金NSFC:ZJNSF LY20A010014。