奇偶符号Harary图的rna数

The rna Number of Parity Signed Harary Graph

摘要: 奇偶符号图的概念最初是由Acharya和Kureethara提出的，随后有Zaslavsky等人相继研究。设(G,σ)是n个顶点的符号图，如果能够对(G,σ)中的个顶点等价转换得到(G,+)，则称(G,σ)是一个奇偶符号图，并称σ是G的一个奇偶符号。Σ^-(G)定义为在图G的所有可能奇偶符号σ下，(G,σ)的负边数的集合。图G的rna数σ^-(G)定义为：σ^-(G)=minΣ^-(G)。本文研究了Harary图H_k,n的rna数。我们计算出了σ^-(H_3,n)，σ^-(H_4,n)和σ^-(H_k,k+2)的精确值。对于H_k,n的其他情况，我们给出其rna数的一个上下界：。

Abstract: The concept of parity signed graphs was initiated by Acharya and Kureethara very recently and then followed by Zaslavsky etc.. Let (G,σ) be a signed graph on n vertices. If (G,σ) is switch-equivalent to (G,+) at a set of many vertices, then we call (G,σ) a parity signed graph and a parity-signature. Σ^-(G) is defined as the set of the number of negative edges of over all possible parity-signatures σ. The rna number σ^-(G) of G is given by σ^-(G)=minΣ^-(G). In this paper, we study the rna number of Harary graph H_k,n. We obtain the exact values of σ^-(H_3,n), σ^-(H_4,n) and σ^-(H_k,k+2). For the remaining case of H_k,n, we prove an upper bound and a lower bound of its rna number: .

1. 引言

我们考虑的是有限的、简单的且连通的图。符号图是图的一类延伸，近几年来对符号图的研究是一个热点，例如，符号图流的问题 [1]，符号图的最小圈覆盖问题 [2]，符号图的同态问题 [3]，符号图的染色问题 [4]，符号图的圆盘染色问题 [5] 等等。符号图的概念最初由Harary [6] 在1953年提出。符号图 $\left(G,\sigma \right)$ 是指图G和定义在图G的边集上的映射 $\sigma$，其中 $\sigma :E\left(G\right)\to \left\{-1,1\right\}$ 称为G的一个符号配置。如果 $\sigma \left(e\right)=1$，记e是正边，否则e就是负边。

奇偶符号图是一种特殊的符号图。奇偶符号图的概念最初是由Acharya和Kureethara [7] 提出的。符号图 $S=\left(G,\sigma \right)$ 称作奇偶符号图，如果存在一个双射 $f:V\left(G\right)\to \left\{1,2,\cdots ,n\right\}$，使得对于图G的每一条边 $e=uv$，若 ${\sigma }^{-}\left(e\right)=1$，则 $f\left(u\right)$ 和 $f\left(v\right)$ 有相同的奇偶性；若 ${\sigma }^{-}\left(e\right)=-1$，则 $f\left(u\right)$ 和 $f\left(v\right)$ 有相反的奇偶性。这里的双射f称为图G (也称为S)的一个奇偶标记， $\sigma$ 称为 $\left(G,\sigma \right)$ 的一个奇偶符号。Acharya、Kureethara和Zaslavsky [8] 刻画了奇偶符号图，其刻画如下：一个符号图S是一个奇偶符号图当且仅当S可以划分成两部分A和B，使得 $\left|\left|A\right|-\left|B\right|\right|\le 1$，并且S的任意两个相邻的顶点u和v在一个集合中当且仅当边uv是正边。在本文中，这种划分 $\left\{A,B\right\}$ 称作奇偶划分。奇偶符号图的这种刻画成立，其原因在于图G的一个奇偶标记可导出对应的一个奇偶划分：

$A=\left\{v\in V\left(G\right):f\left(v\right)是奇数\right\},B=\left\{v\in V\left(G\right):f\left(v\right)是偶数\right\}$

Acharya和Kureethara [7] 定义了奇偶符号图的rna数。设G是一个图， ${\displaystyle \sum {}^{-}\left(G\right)}$ 表示为符号图 $\left(G,\sigma \right)$ 在所有可能奇偶符号 $\sigma$ 下负边数的集合。图G的rna数定义为奇偶符号图 $\left(G,\sigma \right)$ 在所有可能的奇偶标记下负边数最小值，根据定义可以得到： ${\sigma }^{-}\left(G\right)=\min {\displaystyle \sum {}^{-}\left(G\right)}$。

对于 $\text{2}\le k<n$，Harary图 $H_{k,n}$ 的顶点集记为 $V\left(H_{k,n}\right)=\left\{v_0,v_1,\cdots ,v_{n-1}\right\}$，根据k和n的奇偶性，Harary图分为以下三种类型：

类型1：当k是偶数时，记 $k=2r$，两个顶点 $v_i$ 和 $v_j$ 相邻当且仅当 $\left|i-j\right|\le r$。

类型2：当k是奇数，n是偶数时，记 $k=2r+1$，则 $H_{2r+1,n}$ 由 $H_{2r,n}$ 通过添加边 $\left\{v_i{v}_{i+\frac{n}{2}}:i=0,1,\cdots ,\frac{n}{2}-1\right\}$ 得到。

类型3：当k是奇数，n是奇数时，记 $k=2r+1$，则 $H_{2r+1,n}$ 由 $H_{2r,n}$ 通过加边 $\left\{v_i{v}_{i+\frac{n-1}{2}}:i=0,1,\cdots ,\frac{n-1}{2}\right\}$ 得到。

实质上，Harary图 $H_{k,n}$ 是将n个顶点等距离地排成一个环，并且根据k和n的奇偶性向环上加弦。为了方便起见，本文中所有顶点的下标都对模n同余。将Harary图 $H_{k,n}$ 的外环记为 $v_0{v}_1\cdots v_{n-1}{v}_0$，由Harary图 $H_{k,n}$ 的定义，对于第一、二种类型的Harary图 $H_{k,n}$， $H_{k,n}$ 是k-正则的；对于第三种类型的Harary图 $H_{k,n}$，除了一个顶点 $v_{\frac{n-1}{2}}$ 的度是 $k+1$，其余所有顶点的度均是k。当 $k=2$ 时， $H_{k,n}$ 是一个环。因此， ${\sigma }^{-}\left(H_{2,n}\right)={\sigma }^{-}\left(C_n\right)=2$。在本文中，我们只研究 $k>2$ 的情况。首先我们计算了 ${\sigma }^{-}\left(H_{3,n}\right)$， ${\sigma }^{-}\left(H_{4,n}\right)$， ${\sigma }^{-}\left(H_{k,k\text{+}2}\right)$ 的精确值，随后我们给出了三种类型的Harary图 $H_{k,n}$ 的rna数的上下界：

$k\le {\sigma }^{-}\left(H_{k,n}\right)\le \lfloor \frac{kn+n}{4}\rfloor$。

本文用到其他一些数学符号，其定义如下。 $\delta \left(G\right)$， $\kappa \left(G\right)$， ${\kappa }^{\prime }\left(G\right)$ 分别表示图G的最小度，点连通度和边连通度， $G\left[F\right]$ 表示边子集或顶点子集F在图G的导出子图， $G\left[F\right]$ 中的顶点v的度记为 $d_{G\left[F\right]}\left(v\right)$。设 $S=\left(G,\sigma \right)$ 是一个符号图，S的所有负边组成的集合记为 $E^{-}\left(S\right)$。令 $V\left(A\right)$ 和 $V\left(B\right)$ 是图G的两个不相交的点集，记 $E_G\left(A,B\right)$ 表示为连接 $V\left(A\right)$ 中的顶点到 $V\left(B\right)$ 中的顶点的边集，当G在上下文已经明确时，简写为 $E\left(A,B\right)$。

2. 主要结论及其证明

引理1 ${\sigma }^{-}\left(H_{k,n}\right)\ge k$。

证明 对于Harary图 $H_{k,n}$ 来说，有 $\delta \left(H_{k,n}\right)=\kappa \left(H_{k,n}\right)={\kappa }^{\prime }\left(H_{k,n}\right)=k$，由rna数的定义知， ${\sigma }^{-}\left(H_{k,n}\right)\ge {\kappa }^{\prime }\left(H_{k,n}\right)=k$。

引理2 在 $H_{k,n}$ ( $H_{2,3}$ 除外)的奇偶划分 $\left\{A,B\right\}$ 下，边割集 $E\left(A,B\right)$ 的导出子图不可能是一个星。

证明 假设 $E\left(A,B\right)$ 的导出子图是一个星。不妨假设v是该星的中心且 $v\in A$。则对于 $H_{k,n}$ 的任意一个圈C，若C含有B中的点，则 $V\left(C\right)\cap A\subseteq \left\{v\right\}$。特别地，记 $H_{k,n}$ 的外环仅包含A中最多一个顶点，与Harary图的外环包含 $H_{k,n}$ 的所有顶点这个事实矛盾。故假设不成立，即 $E\left(A,B\right)$ 的导出子图不可能是一个星。

引理3 $H_{k,n}$ 在任意一个奇偶划分下，边割集长度不可能是3。

证明 对于 $k=2$ 时，在任意一个奇偶划分下， $H_{k,n}$ 的边割集长度一定是偶数。对于 $k>2$ 的情况，我们从Harary三种类型的图出发证明引理。假设存在一种奇偶划分 $\left\{A,B\right\}$，其中 $\left|A\right|=\lceil \frac{n}{2}\rceil$， $\left|B\right|=\lfloor \frac{n}{2}\rfloor$，使得 $\left|E\left(A,B\right)\right|=3$。

情形1 当 $H_{k,n}$ 为Harary图的第一种类型时，此时k为偶数，由握手定理， ${\displaystyle \underset{v\in A}{\sum }{d}_A\left(v\right)=k\cdot \lceil \frac{n}{2}\rceil }-\left|E\left(A,B\right)\right|$ 的值是偶数，则 $\left|E\left(A,B\right)\right|$ 的值一定是偶数，因此，边割集长度不可能是3。

情形2 当 $H_{k,n}$ 为Harary图的第二种类型时。当 $\frac{n}{2}$ 为偶数时，由握手定理， ${\displaystyle \underset{v\in A}{\sum }{d}_A\left(v\right)=k\cdot \lceil \frac{n}{2}\rceil }-\left|E\left(A,B\right)\right|$ 的值是偶数，则 $\left|E\left(A,B\right)\right|$ 的值一定是偶数。因此，我们讨论当 $\frac{n}{2}$ 为奇数时的情况。

情形2.1 当 $k=3$ 时，易知 $\left|\left\{v_0{v}_1\cdots v_{n-1}{v}_0\right\}\cap E\left(A,B\right)\right|=2$。设 $v_i\in A$， $v_{i+1}\in B$， $0\le i\le \frac{n}{2}-1$。如果 $v_{i+\frac{n}{2}}\in B$，由引理2，则 $v_{i-1}\in A$，并且 $v_{i+\frac{n}{2}-1}\in A$，此时 $\left\{v_i{v}_{i+1},v_i{v}_{i+\frac{n}{2}},v_{i+\frac{n}{2}}{v}_{i+\frac{n}{2}-1}\right\}\subseteq E\left(A,B\right)$，由假设 $\left|E\left(A,B\right)\right|=3$，则 $\left\{v_{i-2},v_{i-3},\cdots ,v_0,v_{n-1},v_{n-2},\cdots ,v_{i+2}\right\}\subseteq A$，而此时 $v_{i+2}{v}_{i+1}\in E\left(A,B\right)$，与 $\left|E\left(A,B\right)\right|=3$ 矛盾，故有 $v_{i+\frac{n}{2}}\in A$，同理可得 $v_{i+\frac{n}{2}+1}\in B$，此时 $\left\{v_i{v}_{i+1},v_{i+\frac{n}{2}}{v}_{i+\frac{n}{2}+1}\right\}\subseteq E\left(A,B\right)$，则有 $v_{i+\frac{n}{2}+1}\in A$， $v_{i+\frac{n}{2}+2}\in B$，而此时 $v_{i+\frac{n}{2}+1}{v}_{i+\frac{n}{2}+2}\in E\left(A,B\right)$，与 $\left|\left\{v_0{v}_1\cdots v_{n-1}{v}_0\right\}\cap E\left(A,B\right)\right|=2$ 矛盾。

情形2.2 当 $k>3$ 时，根据引理1， ${\sigma }^{-}\left(H_{k,n}\right)>3$，所以 $H_{k,n}$ 在奇偶划分下，边割集长度不可能是3。

情形3 当 $H_{k,n}$ 为Harary图的第三种类型时。

情形3.1 当 $k=3$ 时，易知 $\left|\left\{v_0{v}_1\cdots v_{n-1}{v}_0\right\}\cap E\left(A,B\right)\right|=2$。不妨设 $v_i\in A$， $v_{i+1}\in B$， $0\le i\le \frac{n-1}{2}$ 如果 $v_{i+\frac{n-1}{2}}\in B$，由引理2，则 $v_{i-1}\in A$， $v_{i+\frac{n-3}{2}}\in A$，此时 $\left\{v_i{v}_{i+1},v_i{v}_{i+\frac{n-1}{2}},v_{i+\frac{n-1}{2}}{v}_{i+\frac{n-3}{2}}\right\}\subseteq E\left(A,B\right)$，要满足条件 $\left|E\left(A,B\right)\right|=2$，则 $\left\{v_{i-2},v_{i-3},\cdots ,v_0,v_{n-1},v_{n-2},\cdots ,v_{i+2}\right\}\subseteq A$，而此时 $v_{i+2}{v}_{i+1}\in E\left(A,B\right)$，与 $\left|E\left(A,B\right)\right|=3$ 矛盾，故 $v_{i+\frac{n-1}{2}}\in A$，同理 $v_{i+\frac{n+1}{2}}\in B$，此时 $\left\{v_i{v}_{i+1},v_{i+\frac{n-1}{2}}{v}_{i+\frac{n+1}{2}}\right\}\subseteq E\left(A,B\right)$，则 $v_{i+\frac{n-3}{2}}\in A,v_{i+\frac{n-5}{2}}\in A,\cdots ,v_{i+2}\in A$，于是 $v_{i+2}{v}_{i+1}\in E\left(A,B\right)$，与假设矛盾，故 $k=3$ 时， $H_{3,n}$ 在奇偶划分下，边割集长度不可能是3。

情形3.2 当 $k>3$ 时，根据引理1， ${\sigma }^{-}\left(H_{k,n}\right)>3$，所以 $H_{k,n}$ 在奇偶划分下，边割集长度不可能是3。

综上所述 $H_{k,n}$ 在任意一个奇偶划分下，边割集长度不可能是3。

定理2 ${\sigma }^{-}\left(H_{3,n}\right)=\{\begin{array}{ll}4,\hfill & 其他\hfill \\ 5,\hfill & \frac{n}{2}为奇数\hfill \end{array}$

证明 $H_{3,n}$ 只可能为Harary图的第二种类型和第三种类型，因此我们分为以下两种情形考虑。

情形1 当 $H_{3,n}$ 为Harary图的第二种类型时。

情形1.1 当 $\frac{n}{2}$ 为偶数时，由引理3， ${\sigma }^{-}\left(H_{3,n}\right)\ge 4$，下面我们来证明 ${\sigma }^{-}\left(H_{3,n}\right)=4$。我们给出一个Harary图的奇偶标记使得 $H_{3,n}$ 恰好包括4条负边。设 $f:V\left(H_{3,n}\right)\to \left\{1,2,\cdots ,n\right\}$ 定义如下：

$f\left(v_i\right)=\{\begin{array}{ll}2i+1,\hfill & 0\le i\le \frac{n}{4}-1\hfill \\ 2i-\frac{n}{4}-1,\hfill & \frac{n}{4}\le i\le \frac{n}{2}-1\hfill \\ 2i-\frac{n}{2}+1,\hfill & \frac{n}{2}\le i\le \frac{3n}{4}-1\hfill \\ 2i-\frac{3}{4}n,\hfill & \frac{3}{4}n\le i\le n-1\hfill \end{array}$

由映射易知，f是一个奇偶标记，可导出对应的奇偶划分：

$A=\left\{v_0,v_1,\cdots ,v_{\frac{n}{4}-1},v_{\frac{n}{2}},v_{\frac{n}{2}+1},v_{\frac{3n}{4}-1}\right\}$， $B=\left\{v_{\frac{n}{4}},v_{\frac{n}{4}+1},\cdots ,v_{\frac{n}{2}-1},v_{\frac{3n}{4}},v_{\frac{3n}{4}+1},v_{n-1}\right\}$，

此时 $E\left(A,B\right)=\left\{v_{\frac{n}{4}-1}{v}_{\frac{n}{4}},v_{\frac{\text{3}n}{4}-1}{v}_{\frac{\text{3}n}{4}},v_{\frac{n}{\text{2}}-1}{v}_{\frac{n}{\text{2}}},v_{\text{0}}{v}_{n-1}\right\}$，所以 ${\sigma }^{-}\left(H_{3,n}\right)=4$。

情形1.2 当 $\frac{n}{2}$ 为奇数时，设有奇偶划分 $\left\{A,B\right\}$，由握手定理， ${\displaystyle \underset{v\in A}{\sum }{d}_A\left(v\right)=3\cdot \frac{n}{2}}-\left|E\left(A,B\right)\right|$ 的值是一个偶数，则 $\left|E\left(A,B\right)\right|$ 的值一定是奇数，再结合引理3， ${\sigma }^{-}\left(H_{3,n}\right)\ge 5$，下面我们来证明 ${\sigma }^{-}\left(H_{3,n}\right)=5$。我们给出一个Harary图的奇偶标记使得 $H_{3,n}$ 恰好包括5条负边。设 $f:V\left(H_{3,n}\right)\to \left\{1,2,\cdots ,n\right\}$ 定义如下：

$f\left(v_i\right)=\{\begin{array}{l}\begin{array}{cc}2i+1,& 0\le i\le \frac{n}{4}-\frac{1}{2}\end{array}\hfill \\ \begin{array}{cc}2i-\frac{n}{4}-\frac{5}{2},& \frac{n}{4}+\frac{1}{2}\le i\le \frac{n}{2}-1\end{array}\hfill \\ \begin{array}{cc}2i-\frac{n}{2}+2,& \frac{n}{2}\le i\le \frac{3n}{4}-\frac{3}{2}\end{array}\hfill \\ \begin{array}{cc}2i-\frac{3}{4}n-\frac{3}{2},& \frac{3}{4}n-\frac{1}{2}\le i\le n-1\end{array}\hfill \end{array}$

由映射易知，f是一个奇偶标记，可导出对应的一个奇偶划分：

$A=\left\{v_0,v_1,\cdots ,v_{\frac{n}{4}-\frac{1}{2}},v_{\frac{n}{2}},v_{\frac{n}{2}+1},v_{\frac{3n}{4}-\frac{3}{2}}\right\}$， $B=\left\{v_{\frac{n}{4}+\frac{1}{2}},v_{\frac{n}{4}+\frac{3}{2}},\cdots ,v_{\frac{n}{2}-1},v_{\frac{3n}{4}-\frac{1}{2}},v_{\frac{3n}{4}+1},v_{n-1}\right\}$。

因此， $E\left(A,B\right)=\left\{v_{\frac{n}{4}-\frac{1}{2}}{v}_{\frac{n}{4}+\frac{1}{2}},v_{\frac{\text{3}n}{4}-\frac{3}{2}}{v}_{\frac{\text{3}n}{4}-\frac{1}{2}},v_0{v}_{n-1},v_{\frac{n}{2}-1}{v}_{\frac{n}{2}},v_{\frac{n}{4}-\frac{1}{2}}{v}_{\frac{3n}{4}-\frac{1}{2}}\right\}$，所以 ${\sigma }^{-}\left(H_{3,n}\right)=5$。

情形2 当 $H_{3,n}$ 为Harary图的第三种类型时，由引理3， ${\sigma }^{-}\left(H_{3,n}\right)\ge 4$，下面我们来证明 ${\sigma }^{-}\left(H_{3,n}\right)=4$。我们给出一个Harary图的奇偶标记使得 $H_{3,n}$ 恰好包括4条负边。给定 $H_{3,n}$ 一个奇偶划分 $\left\{A,B\right\}$ ：

$B=\left\{v_1,v_2,\cdots ,v_{\frac{n-1}{4}},v_{\frac{n+1}{2}},v_{\frac{n+3}{2}},\cdots ,v_{\frac{3n-3}{4}}\right\},A=H_{3,n}\backslash B$，

此时 $E\left(A,B\right)=\left\{v_0{v}_1,v_{\frac{n-1}{2}}{v}_{\frac{n+1}{2}},v_{\frac{n-1}{4}}{v}_{\frac{n+3}{4}},v_{\frac{3n-3}{4}}{v}_{\frac{3n+1}{4}}\right\}$，所以 ${\sigma }^{-}\left(H_{3,n}\right)=4$。

引理4 $H_{4,n}$ 在任意一个奇偶划分下，边割集长度不可能是4。

证明 假设 $H_{4,n}$ 存在一种的奇偶划分 $\left\{A,B\right\}$，其中 $\left|A\right|=\lceil \frac{n}{2}\rceil$， $\left|B\right|=\lfloor \frac{n}{2}\rfloor$，使得 $\left|E\left(A,B\right)\right|=4$。

情形1 $\left|\left\{v_0{v}_1\cdots v_{n-1}{v}_0\right\}\cap E\left(A,B\right)\right|=2$。不妨设 $v_i\in A$， $v_{i+1}\in B$， $0\le i\le n-1$。因为 $E\left(A,B\right)$ 包含 $H_{4,n}$ 的两条弦，则这两条弦的端点可分为如下四种子情况。

情形1.1 如果这两条弦的两个端点分别为 $v_i$， $v_{i+1}$，假设 $v_{i+2}\in B$， $v_{i+3}\in A$，此时 $\left\{v_i{v}_{i+1},v_{i+2}{v}_{i+3}\right\}\subseteq E\left(A,B\right)$，则 $v_{i-1}\in B$， $v_{i-1}{v}_i\in E\left(A,B\right)$，与 $\left|\left\{v_0{v}_1\cdots v_{n-1}{v}_0\right\}\cap E\left(A,B\right)\right|=2$ 矛盾，故假设不成立。假设 $v_{i-2}\in B$， $v_{i+3}\in A$， $v_{i+2}\in A$，则 $A=H_{4,n}\backslash \left\{v_{i+1},v_{i-2}\right\}$，与奇偶划分矛盾，故假设不成立。如果 $v_{i-2}\in B$， $v_{i+3}\in A$， $v_{i+2}\in B$，则 $\left\{v_{i+3},v_{i+5}\right\}\subseteq A$， $v_{i+4}\in B$，此时 $\left\{v_i{v}_{i+1},v_{i+2}{v}_{i+3},v_{i+4}{v}_{i+5}\right\}\subseteq E\left(A,B\right)$，与 $\left|\left\{v_0{v}_1\cdots v_{n-1}{v}_0\right\}\cap E\left(A,B\right)\right|=2$ 矛盾，故情形1.1不存在。

情形1.2 如果这两条弦的共同的端点为 $v_i$， $v_{i+1}$ 中其中一个顶点时，不妨设这个端点为 $v_i$。根据引理2， $v_{i-1}\in A$，此时 $\left\{v_{i-1}{v}_{i+1},v_i{v}_{i-2},v_i{v}_{i+2}\right\}\subseteq E\left(A,B\right)$，与 $E\left(A,B\right)$ 包含 $H_{4,n}$ 的两条弦矛盾。故情形1.2不存在。

情形1.3 如果 $v_i$ 、 $v_{i+1}$ 中只有一个顶点作为这两条弦的端点时，不妨设 $v_i$ 为其中一条弦的端点并且 $v_{i+2}\in B$，则 $v_{i-1}\in B$， $v_{i-2}\in A$，此时 $\left\{v_i{v}_{i+1},v_{i-1}{v}_{i-2},v_{i-1}{v}_i\right\}\subseteq E\left(A,B\right)$，与假设矛盾。故情形1.3不存在。

情形1.4 如果 $v_i$， $v_{i+1}$ 均不作为这两条弦的端点，则有 $v_{i+2}\in A$， $v_{i+3}\in B$，此时 $\left\{v_i{v}_{i+1},v_{i+1}{v}_{i+2},v_{i+2}{v}_{i+3}\right\}\subseteq E\left(A,B\right)$，与假设矛盾。故情形1.4不存在。

情形2 $\left|\left\{v_0{v}_1\cdots v_{n-1}{v}_0\right\}\cap E\left(A,B\right)\right|=4$。不妨设 $v_i\in A$， $v_{i+1}\in B$， $0\le i\le n-1$，易知 $\left\{v_{i+2},v_{i+4}\right\}\subseteq A$，则 $\left\{v_i{v}_{i+1},v_{i+1}{v}_{i+2},v_{i+2}{v}_{i+3},v_{i+3}{v}_{i+4},v_{i+4}{v}_{i+5}\right\}\subseteq E\left(A,B\right)$，矛盾。

综上所述 $H_{4,n}$ 在任意一个奇偶划分下，边割集长度不可能是4。

定理3 ${\sigma }^{-}\left(H_{4,n}\right)=6$。

证明 假设 $H_{4,n}$ 存在一种的奇偶划分 $\left\{A,B\right\}$ 使得 $\left|A\right|\text{=}\lceil \frac{n}{2}\rceil$，则 ${\displaystyle \underset{v\in A}{\sum }{d}_A\left(v\right)=4\cdot \lceil \frac{n}{2}\rceil }-\left|E\left(A,B\right)\right|$ 的值是偶数，则 $\left|E\left(A,B\right)\right|$ 的值一定是偶数，再结合引理4， ${\sigma }^{-}\left(H_{k,n}\right)\ge 6$，下面我们来证明 ${\sigma }^{-}\left(H_{k,n}\right)=6$。我们给出一个Harary图的奇偶标记使得 $H_{4,n}$ 恰好包括6条负边。设 $f:V\left(H_{4,n}\right)\to \left\{1,2,\cdots ,n\right\}$ 定义如下：

$f\left(v_i\right)=\{\begin{array}{ll}2i+2,\hfill & 1\le i\le \lceil \frac{n-\text{1}}{2}\rceil -1\hfill \\ 2i-n-1,\hfill & \lceil \frac{n-\text{1}}{2}\rceil \le i\le n-1\hfill \end{array}$

由映射易知，f是一个奇偶标记，我们可以写出相应的负边集合：

$\left\{v_0{v}_{n-1},v_0{v}_{n-2},v_1{v}_{n-1},v_{\lceil \frac{n-1}{2}\rceil -2}{v}_{\lceil \frac{n-1}{2}\rceil },v_{\lceil \frac{n-1}{2}\rceil -1}{v}_{\lceil \frac{n-1}{2}\rceil +1},v_{\lceil \frac{n-1}{2}\rceil -1}{v}_{\lceil \frac{n-1}{2}\rceil }\right\}$，

所以 ${\sigma }^{-}\left(H_{k,n}\right)=6$。

定理4 对任意的正整数 $r\ge 2$，

${\sigma }^{-}\left(H_{2r-2,2r}\right)=r^2-r$。

证明 对于图 $H_{2r-2,2r}$ 来说，设 $f:V\left(H_{2r-2,2r}\right)\to \left\{1,2,\cdots ,2r\right\}$ 定义如下：

$f\left(v_i\right)=\{\begin{array}{ll}2i+1,\hfill & 0\le i\le r-1\hfill \\ 2i+1-n,\hfill & r\le i\le 2r-1\hfill \end{array}$

由映射易知，f是一个奇偶标记，可导出对应的一个奇偶划分：

$A=\left\{v_0,v_1,\cdots ,v_{r-1}\right\},B=\left\{v_r,v_{r+1},\cdots ,v_{2r-1}\right\}$，

这里 $H_{2r-2,2r}\left[A\right]$， $H_{2r-2,2r}\left[B\right]$ 均是两个完全图 $K_r$，因此在这种奇偶划分下，边割集长度一定最小，因此，

${\sigma }^{-}\left(G\right)=E\left(A,B\right)=\frac{\left(2r-2\right)\cdot 2r}{2}-\frac{r\cdot \left(r-1\right)}{2}\cdot 2=r^2-r$。

定理5 对任意的正整数 $r\ge 2$，有

${\sigma }^{-}\left(H_{2r-1,2r+1}\right)=r^2$。

证明 设 $H_{2r-1,2r\text{+1}}$ 环上的点依次为 $v_0,v_1,\cdots ,v_{2r}$。记 $A=\left\{v_0,v_1,\cdots ,v_r\right\}$， $B=\left\{v_{r+1},v_{r+2},\cdots ,v_{2r}\right\}$。则 $\left\{A.B\right\}$ 为 $H_{2r-1,2r+1}$ 的一种奇偶划分。容易看出， $H_{2r-1,2r+1}\left[A\right]$， $H_{{}_{2r-1,2r+1}}\left[B\right]$ 分别是两个完全图 $K_{r+1}$， $K_r$。因此，在这种奇偶划分下，边割集长度一定最小。因此，

${\sigma }^{-}\left(H_{2r-1,2r+1}\right)=\left|E\left(A,B\right)\right|=\frac{\left(2r-1\right)\cdot \left(2r+1\right)+1}{2}-\frac{\left(r+1\right)\cdot r}{2}-\frac{\left(r-1\right)\cdot r}{2}=r^2$。

Ligang Jin和Xiaoyue Chen [9] 给出了对于任意一个图G的rna数的上界：对于 $n\left(n\ge 4\right)$ 个顶点，m条边的图G， ${\sigma }^{-}\left(G\right)\le \lfloor \frac{m}{2}+\frac{n}{4}\rfloor$，当且仅当 $G=K_n$ 或 $K_n-e$ 或 $K_n-\Delta$ 时等式成立。现在将这个上界应用到Harary图上。

引理5 对于任意的 $k,n$，有 $k\le {\sigma }^{-}\left(H_{k,n}\right)\le \lfloor \frac{kn+n}{4}\rfloor$。

证明 下界由引理1， ${\sigma }^{-}\left(H_{k,n}\right)\ge k$。上界代入公式 ${\sigma }^{-}\left(G\right)\le \lfloor \frac{m}{2}+\frac{n}{4}\rfloor$。对于第一、二种类型的Harary图来说， $m=\frac{kn}{2}$，因此 ${\sigma }^{-}\left(G\right)\le \lfloor \frac{kn+n}{4}\rfloor$ ；对于第三种类型的Harary图来说， $m=\frac{kn+1}{2}$，因此 ${\sigma }^{-}\left(H_{k,n}\right)\le \lfloor \frac{kn+1+n}{4}\rfloor =\lfloor \frac{kn+n}{4}\rfloor$。

3. 总结与展望

本文研究了Harary图的rna数，我们通过分析Harary图的结构性质，计算出了一些特殊类型Harary图rna数的精确值，并且借助文献 [8] 中的结论给出了Harary图rna数的上下界。值得注意的是，从 ${\sigma }^{-}\left(H_{3,n}\right)$， ${\sigma }^{-}\left(H_{4,n}\right)$， ${\sigma }^{-}\left(H_{k,k+2}\right)$ 的值可以看出，本文中给出Harary图rna数的下界不是紧的，这还需要我们继续加以改进。

基金项目

国家自然科学基金NSFC：ZJNSF LY20A010014。