ABSTRACT

Let G be a simple connected graph with a perfect matching, S an edge set of G. We call S an anti- forcing set of G, if contains only one perfect matching of G. The cardinality of the minimum anti-forcing set of G is called the anti-forcing number of G. In this paper, we study the anti-forcing number of the Cartesian product of a cycle and a path. According to the necessity of a graph with only one perfect matching, we show that the anti-forcing numbers of are all, and the anti-forcing number of is 3.

Keywords:The Cartesian Product of a Cycle and a Path, Perfect Matching, Anti-Forcing Numbers

关于的反强迫数

张勇军，蔡金转^*

海南大学数学系，海南 海口

收稿日期：2016年8月15日；录用日期：2016年8月27日；发布日期：2016年8月30日

摘 要

设是一个有完美匹配的简单连通图。若的一个边子集满足只有唯一完美匹配，则称是的一个反强迫集。中最小的反强迫集的大小称为的反强迫数。本文主要研究圈和路的卡什积图的反强迫数。根据一个图有唯一完美匹配的必要条件，我们证明了，，的反强迫数都为，并表明了的反强迫数恒为3。

关键词 :圈和路的卡什积图，完美匹配，反强迫数

1. 引言

图的完美匹配是指覆盖了的所有顶点的一个独立边集，它对应于化学中的凯库勒结构。Randic和Klein对凯库勒结构提出了内自由度的概念 [1] [2] ，图的完美匹配对应地也有强迫数这一概念 [3] 。一个边集称为图的完美匹配的强迫集是指只包含在中，但不包含在其它完美匹配中。的最小的强迫集的大小称为的强迫数。近年来，化学图论专家针对图的完美匹配又陆续提出了强迫六角形，全局强迫数，反凯库勒数和反强迫数等概念。其中，反强迫数的概念最早是由Vukicevic和Trinajstic提出来的 [4] 。

若图一个边集满足只有唯一完美匹配，则称为图的反强迫集。图最小的反强迫集的大小称为的反强迫数，并用表示。目前，有关反强迫数的结论较少，主要是针对一些图类进行研究。Vukicevic和Trinajstic证明了平行四边形结构六角系统的反强迫数为1 [4] 。随后，六角形链 [5] ，双六角形链 [6] ，一类由四边形和六边形构成的cata型图(cata-condensed Phenylenes) [7] ，富勒烯 [8] ，管状硼氮富勒烯图 [9] 的反强迫数先后得到确定。

设和是两个图。两个图和的卡什积图，记为，是一个以为顶点集的图，且其中顶点和有边相连当且仅当且或且。

本文主要研究圈和路的卡什积图的反强迫数。我们用和分别表示顶点数为和的圈和路。本文第一部分根据非二部图有唯一完美匹配的必要条件，证明了和的反强迫数都为。第二部分根据二部图有唯一完美匹配的必要条件，得到的反强迫数为。对，我们证明了其反强迫数恒为3。

2. 奇长圈和路的卡什积图的反强迫数

为了保证有完美匹配，我们只讨论的情形。此部分主要基于以下关于一个图有唯一完美匹配的必要条件。

引理2.1 [10] 若一个连通图恰好有一个完美匹配，则有一条割边属于此完美匹配。

定理2.2

证明 易见，去掉图1中所示的内外两个三角形之间的两条虚线标记的边后，因为内外两个三角形之间必须有奇数条匹配边，所以内外两个三角形之间剩余的边必须是匹配边，这样我们可确定出的余子图中的唯一完美匹配。于是这两条虚边构成的一个反强迫集，从而。另外，设是的一个最小的反强迫集，则只有唯一完美匹配。根据引理2.1，有一条割边，而的边割大小至少是3，为产生一条割边，至少需要去掉两条边，即。于是得证。■

设为图的一个完美匹配。一个圈称为的-交替圈是指圈中的边由和非的边交替组成。因为通过交换交替圈中的匹配边和非匹配边，我们可以得到的另一个完美匹配，所以我们有以下结论：

图1. 虚线所示边构成一个反强迫集

引理2.3 设为图的一个边子集。若只包含的唯一完美匹配，则没有-交替圈。

为了后面讨论方便，我们先给的点和边进行标记(见图2)，我们称为的第层()，记为。当为奇(偶)数时，我们称为的奇(偶)层。我们称属于某层的边为路边，不属于任一层的边称为圈边。

利用数学归纳法，我们可以证明以下结论：

定理2.4

证明 令(见图2虚线标记的边)，下证为的一个反强迫集。因为的奇数层之间必须有奇数条匹配边，所以第一层中剩余的边必须是匹配边。则此时也可确定为匹配边。又因为在中去掉了，所以中只有可作为匹配边。依次匹配下去，可知的唯一完美匹配(见图2)为，由知。

下面对用数学归纳法证明。

当时，由定理2.2知结论成立。假设结论对所有小于的情形成立，下面对进行讨论。设是的一个最小的反强迫集，则只有唯一完美匹配，记为。下面我们分两种情况进行讨论：

情形1. 存在某个，使得，即偶层不含匹配边。

此时可分解为两个三长圈和路的卡什积图，分别记为和，其中。根据假设，也分解为两部分和，分别为和的完美匹配。记，。因为是的唯一完美匹配，故和也分别为和中的唯一完美匹配。于是和分别为和的反强迫集。根据归纳假设，，。从而。

情形2.的每个偶层都至少有一条边是匹配边。

因为的每个完美匹配只能包含每个偶层的偶数条边，所以与每个偶层都交于恰好2条边。

不妨假设，则，故，依此类推，我们可确定为(见图2)的唯一完

美匹配，交每个偶层恰好两条边，每个奇层一条边。

图2. 定理2.4的证明示意图

注意到匹配边所在的四边形是一个交替圈，根据引理2.3，该四边形的两条圈边至少有一条属于反强迫集。因为共有个偶层，故共有个这样的交替四边形。每个交替四边形至少有一条圈边属于。在每个交替四边形各取一条圈边，记这些圈边构成的集合为，则且。进一步，因为只有唯一完美匹配，根据引理2.1，有一条割边。而的最小边割是3，故至少还需要去掉的两条边才能产生一条割边。于是。

综上，。证毕。■

对于一般奇长圈的卡什积图，我们给出了结论：

定理2.5

证明 标记的点和边(见图3(a))。令，则有两条悬挂边(一条边称为一个图的悬挂边是指该边恰有一个端点度数为1)可先确定为匹配边，接着可确定为匹配边，依次匹配下去，直到点，它只能与匹配。接着确定匹配边，依次匹配下去可确定中的唯一完美匹配。则是一个反强迫集，。

下证：设是的一个最小反强迫集，是的唯一完美匹配。设恰有条路边为匹配边(为奇数)。除这条边，其余匹配边都是圈边并且包含在个不交的-交替4边形中。根据引理2.3，这些-交替4边形至少有一条路边属于。在每个交替四边形各取一条路边，记这些路边构成的集合为，则且。另外，当时，任两条相邻的匹配路边和它们之间的所有圈边也构成一个-交替圈。根据引理2.3，这些-交替圈至少有一条非匹配的圈边属于 (见图3(b))，于是。而当时，该匹配路边和的所有匹配圈边也确定一个-交替圈，且该圈不交于 (见图3(c))。根据引理2.3，该-交替圈至少有一条非匹配的边属于，于是。■

图3. 定理2.5的证明示意图

3. 偶长圈和路的卡什积图的反强迫数

此部分主要基于以下关于一个二部图有唯一完美匹配的必要条件。

引理3.1 [10] 设是一个只有唯一完美匹配的二部图，则的点可标记为使得每条边。

推论3.2 若一个连通二部图恰好有一个完美匹配，则有两个一度点。

证明 设。因为恰好有一个完美匹配，根据引理3.1，的点可标记为，使得每条边。于是的邻点只有，的邻点只有，即和为的两个一度点。■

因为是一个偶长圈，恰有两个完美匹配，故其反强迫集至少包含一条边。另外，去掉其任意一条边，剩余子图只有一个完美匹配，故我们可得以下结论：

定理3.3

定理3.4

证明 易见，去掉图4中所示的三条虚线标记边后，的余子图只有唯一完美匹配，于是。另外，设是的一个最小的反强迫集，则只有唯一完美匹配，记为。因为是二部图，根据推论3.2，有两个一度点，而是3-正则图，为产生两个一度点，至少需要去掉三条边，即。于是得证。■

下面我们开始讨论的反强迫数。为了讨论方便，我们先给的点和边进行标记(见图5)，我们称为的第层，记为()。类似地，我们可定义的奇层，偶层和路边，圈边。

定理3.5

证明 若为偶数，令。则可知

中的悬挂边和为匹配边，依次匹配下去，知是唯一完美匹配(见图5(a))。

若为奇数，则令，同样可得是唯一完美匹配(见图5(b))。

不论哪种情况，都有，故。下面对用归纳证明()。

当时，由定理3.4知结论成立。假设结论对所有大于2且小于的情形都成立，下面对进行讨论。设是的一个最小的反强迫集，则只有唯一完美匹配，记为。下面我们分情况进行讨论：

图4. 定理3.4的证明示意图

图5. 定理3.5的证明示意图

情形1. 存在某个，使得，即的第层的四条边都不在中。

可分解为两个四长圈和路的卡什积图，分别记为和。

根据假设，也可分解为两部分和，分别为和的完美匹配。记，。因为是的唯一完美匹配，故和也分别为和中的唯一完美匹配。这说明和分别为和的反强迫集。

当或时，中有一个四边形。不妨设为四边形。根据定理3.3，。又，根据归纳假设，。从而。

当且时，设，。根据归纳假设，，。于是。

情形2. 存在某个，使得，即的第层的四条边都不在中。这时与的相邻的层只能有0条匹配边，该情形即为情形1。

情形3. 对每个，，且。

因为的每个完美匹配只能与每层交于偶数条边，则与每层都交于恰好2条边。根据这两条匹配边的位置，下面分两种子情形进行讨论：

1) 若存在某一层，其两条匹配边位于该层的相对位置(见图6)。

不妨设中。因为只有两条匹配边，则。于是。而只能有两条匹配边，且这两条匹配边也是位于相对位置。类似地，我们可推出在每层的2条匹配边都位于相对位置。但进行到第一层时，会产生两个不相邻的点(见图6)，其邻点已跟其它点匹配，这与是完美匹配矛盾。

图6. 定理3.5情形3(1)的证明示意图

图7. 定理3.5情形3(2)的证明示意图

图8. 定理3.6的证明示意图

2)与任意一层的两条匹配边都位于相近位置(见图7)。

不妨设中。因为只有两条匹配边，则。于是是仅有的两条匹配边。依次类推，可知在奇数层，我们有。而在偶数层，我们有。于是当为偶数时，我们可确定中的唯一完美匹配为 (见图7(a))；而当为奇数时，中的唯一完美匹配为(见图7(b))。

注意到的第1层的两条匹配边所在的四边形是一个交替圈，根据引理2.3，该四边形的两条圈边至少有一条属于反强迫集。的每层都有一个这样的交替四边形，而每个交替四边形至少有一条圈边属于，我们在每个交替四边形各取一条圈边，记这些圈边构成的集合为，则且。

当为偶数时，令(见图7(a))。而当为奇数时，令 (见图7(b))。可见是一个中的交替圈，根据引理2.3，中至少有一条非匹配边属于。任取中属于的一条非匹配边，记为。但不论取上哪一条非匹配边，都有且中顶点的最小度仍为2。根据推论3.2，有两个一度点。因为在中至少还要去掉一条边才能产生一度点，从而除了包含，还包含另外一条边。于是。

综上，。证毕。■

对于一般的偶圈的卡什积图，我们得到其反强迫数如下：

定理3.6

证明 先证：将的点和边进行标记(见图8)。令，则有两条悬挂边可先确定为匹配边，依次匹配下去，可确定完美匹配。再证：根据推论3.2，去掉一个反强迫集后要有两个一度点。因为是3-正则的简单图，所以至少需要去掉3条边才可能产生两个一度点，因此。综上，。■

基金项目

海南省自然科学基金资助项目(114001)，海南省自然科学基金资助项目(2016CXTD004)。

文章引用

张勇军,蔡金转. 关于C_m×P_k的反强迫数
On the Anti-Forcing Number of C_m×P_k[J]. 应用数学进展, 2016, 05(03): 435-442. http://dx.doi.org/10.12677/AAM.2016.53054

参考文献 (References)