AAM  >> Vol. 5 No. 3 (August 2016)

作者:  

张勇军,蔡金转:海南大学数学系,海南 海口

关键词:
圈和路的卡什积图完美匹配反强迫数The Cartesian Product of a Cycle and a Path Perfect Matching Anti-Forcing Numbers

摘要:
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.

文章引用:
张勇军, 蔡金转. 关于Cm×Pk的反强迫数[J]. 应用数学进展, 2016, 5(3): 435-442. http://dx.doi.org/10.12677/AAM.2016.53054

参考文献

[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.