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

• 全文下载: PDF(637KB)    PP.435-442   DOI: 10.12677/AAM.2016.53054
• 下载量: 224  浏览量: 256

G 是一个有完美匹配的简单连通图。若G 的一个边子集S 满足G-S 只有唯一完美匹配，则称SG 的一个反强迫集。G 中最小的反强迫集的大小称为G 的反强迫数。本文主要研究圈和路的卡什积图的反强迫数。根据一个图有唯一完美匹配的必要条件，我们证明了C3×P2kC2K+1×P2C4×P 的反强迫数都为k+1，并表明了C2k×P2 (k≥2) 的反强迫数恒为3。

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 G-S 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 C3×P2kC2K+1×P2C4×P are all k+1 , and the anti-forcing number of C2k×P2 (k≥2) is 3.

 [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] 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] 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] 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] Deng, H. (2007) The Anti-Forcing Number of Hexagonal Chains. MATCH Communications in Mathematical and in Computer Chemistry, 58, 675-682. [6] Deng, H. (2008) The Anti-Forcing Number of Double Hexagonal Chains. MATCH Communications in Mathematical and in Computer Chemistry, 60, 183-192. [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] 杨琴. 富勒烯图的反凯库勒数和反强迫数[D]: [硕士学位论文]. 兰州: 兰州大学, 2010. [9] 蒋晓艳, 程晓胜. 硼氮富勒烯图的反强迫数[J]. 湖北师范学院学报(自然科学版), 2013, 33(3): 28-30. [10] Lovasz, L. and Plummer, M.D. (1986) Matching Theory. Annals of Discrete Mathematics Vol. 29, North-Holland, Amsterdam.