﻿ 关于Cm×Pk的反强迫数 On the Anti-Forcing Number of Cm×Pk

Advances in Applied Mathematics
Vol.05 No.03(2016), Article ID:18438,8 pages
10.12677/AAM.2016.53054

On the Anti-Forcing Number of

Yongjun Zhang, Jinzhuan Cai*

Department of Mathematics, Hainan University, Haikou Hainan

Received: Aug. 15th, 2016; accepted: Aug. 27th, 2016; published: Aug. 30th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

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

1. 引言

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

Figure 1. The dashed lines form an anti-forcing set

Figure 2. Illustration for the proof of Theorem 2.4

(a) (b) (c)

Figure 3. Illustration for the proof of Theorem 2.5

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

Figure 4. Illustration for the proof of Theorem 3.4

(a) (b)

Figure 5. Illustration for the proof of Theorem 3.5

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

Figure 6. Illustration for the proof of Case 3(1) of Theorem 3.5

(a) (b)

Figure 7. Illustration for the proof of Case 3(2) of Theorem 3.5

Figure 8. Illustration for the proof of Theorem 3.6

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

On the Anti-Forcing Number of Cm×Pk[J]. 应用数学进展, 2016, 05(03): 435-442. http://dx.doi.org/10.12677/AAM.2016.53054

1. 1. Klein, D. and Randic, M. (1987) Innate Degree of Freedom of a Graph. Journal of Computational Chemistry, 8, 516-521. http://dx.doi.org/10.1002/jcc.540080432

2. 2. Randic, M. and Klein, D. (1985) Kekule Valence Structures Revisited. Innate Degrees of Freedom of π-Electron Couplings. In: Trinajstic, N., Ed., Mathematics and Computational Concepts in Chemistry, Hor-wood/Wiley, New York, 274-282.

3. 3. Harary, F., Klein, D. and Zivkovic, T. (1991) Graphical Properties of Polyhexes: Perfect Matching Vector and Forcing. Journal of Mathematical Chemistry, 6, 295-306. http://dx.doi.org/10.1007/BF01192587

4. 4. Vukicevic, D. and Trinajstic, N. (2007) On the Anti-Forcing Number of Benzenoids. Journal of Mathematical Chemistry, 42, 575-583. http://dx.doi.org/10.1007/s10910-006-9133-6

5. 5. Deng, H. (2007) The Anti-Forcing Number of Hexagonal Chains. MATCH Communications in Mathematical and in Computer Chemistry, 58, 675-682.

6. 6. Deng, H. (2008) The Anti-Forcing Number of Double Hexagonal Chains. MATCH Communications in Mathematical and in Computer Chemistry, 60, 183-192.

7. 7. Zhang, Q., Bian, H. and Vumar, E. (2011) On the Anti-Kekule and Anti-Forcing Number of Cata-Condensed phenylenes. MATCH Communications in Mathematical and in Computer Chemistry, 65, 799-806.

8. 8. 杨琴. 富勒烯图的反凯库勒数和反强迫数[D]: [硕士学位论文]. 兰州: 兰州大学, 2010.

9. 9. 蒋晓艳, 程晓胜. 硼氮富勒烯图的反强迫数[J]. 湖北师范学院学报(自然科学版), 2013, 33(3): 28-30.

10. 10. Lovasz, L. and Plummer, M.D. (1986) Matching Theory. Annals of Discrete Mathematics Vol. 29, North-Holland, Amsterdam.

*通讯作者。