Advances in Applied Mathematics
Vol.
11
No.
04
(
2022
), Article ID:
50344
,
7
pages
10.12677/AAM.2022.114184
奇偶符号Harary图的rna数
陈晓月,金利刚
浙江师范大学,浙江 金华
收稿日期:2022年3月14日;录用日期:2022年4月8日;发布日期:2022年4月18日
摘要
奇偶符号图的概念最初是由Acharya和Kureethara提出的,随后有Zaslavsky等人相继研究。设
是n个顶点的符号图,如果能够对
中的
个顶点等价转换得到
,则称
是一个奇偶符号图,并称
是G的一个奇偶符号。
定义为在图G的所有可能奇偶符号
下,
的负边数的集合。图G的rna数
定义为:
。本文研究了Harary图
的rna数。我们计算出了
, 和
的精确值。对于
的其他情况,我们给出其rna数的一个上下界:
。
关键词
奇偶符号图,rna数,奇偶划分,Harary图
The rna Number of Parity Signed Harary Graph
Xiaoyue Chen, Ligang Jin
Zhejiang Normal University, Jinhua Zhejiang
Received: Mar. 14th, 2022; accepted: Apr. 8th, 2022; published: Apr. 18th, 2022
ABSTRACT
The concept of parity signed graphs was initiated by Acharya and Kureethara very recently and then followed by Zaslavsky etc.. Let
be a signed graph on n vertices. If
is switch-equivalent to
at a set of
many vertices, then we call
a parity signed graph and
a parity-signature.
is defined as the set of the number of negative edges of
over all possible parity-signatures
. The rna number
of G is given by
. In this paper, we study the rna number of Harary graph
. We obtain the exact values of
, and
. For the remaining case of
, we prove an upper bound and a lower bound of its rna number:
.
Keywords:Parity Signed Graphs, The rna Number, Parity Division, Harary Graph
Copyright © 2022 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
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。
文章引用
陈晓月,金利刚. 奇偶符号Harary图的rna数
The rna Number of Parity Signed Harary Graph[J]. 应用数学进展, 2022, 11(04): 1693-1699. https://doi.org/10.12677/AAM.2022.114184
参考文献
- 1. Raspaud, A. and Zhu, X (2011) Circular Flow on Signed Graphs. Journal of Combinatorial Theory, Series B, 101, 464-479. https://doi.org/10.1016/j.jctb.2011.02.007
- 2. Lu, Y., Cheng, J., Luo, R. and Zhang, C.Q. (2019) Shortest Circuit Covers of Signed Graphs. Journal of Combinatorial Theory, Series B, 134, 164-178. https://doi.org/10.1016/j.jctb.2018.06.001
- 3. Naserasr, R., Sopena, E. and Zaslavsky, T. (2021) Homomorphisms of Signed Graphs: An Update. European Journal of Combinatorics, 91, Article ID: 103222. https://doi.org/10.1016/j.ejc.2020.103222
- 4. Zaslavsky, T. (1982) Signed Graph Coloring. Discrete Mathematics, 39, 215-228.
https://doi.org/10.1016/0012-365X(82)90144-3
- 5. Kang, Y. and Steffen, E. (2018) Circular Coloring of Signed Graphs. Journal of Graph Theory, 87, 135-148.
https://doi.org/10.1002/jgt.22147
- 6. Harary, F. (1953) On the Notion of Balance of a Signed Graph. Michigan Mathematical Journal, 2, 143-146.
https://doi.org/10.1307/mmj/1028989917
- 7. Acharya, M. and Kureethara, J.V. (2021) Parity Labeling in Signed Graphs. Journal of Prime Research in Mathematics, 17, 1-7.
- 8. Acharya, M., Kureethara, J.V. and Zaslavsky, T. (2021) Characterizations of Some Parity Signed Graphs. Australasian Journal of Combinatorics, 81, 89-100.
- 9. Jin, L., Chen, X. and Kang, Y. (2021) A Study on Parity Signed Graphs: The RNA Number.
arXiv:2111.04956 [math.CO]