Mobile version of Hanspub

文章引用说明 更多>> (返回到该文章)

Harary, F., Klein, D. and Zivkovic, T. (1991) Graphical Properties of Polyhexes: Perfect Matching Vector and Forcing. Journal of Mathematical Chemistry, 6, 295-306.


  • 标题: 关于Cm×Pk的反强迫数On the Anti-Forcing Number of Cm×Pk

    作者: 张勇军, 蔡金转

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

    期刊名称: 《Advances in Applied Mathematics》, Vol.5 No.3, 2016-08-30

    摘要: 设G 是一个有完美匹配的简单连通图。若G 的一个边子集S 满足G-S 只有唯一完美匹配,则称S 是G 的一个反强迫集。G 中最小的反强迫集的大小称为G 的反强迫数。本文主要研究圈和路的卡什积图的反强迫数。根据一个图有唯一完美匹配的必要条件,我们证明了C3×P2k,C2K+1×P2,C4×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×P2k,C2K+1×P2,C4×P are all k+1 , and the anti-forcing number of C2k×P2 (k≥2) is 3.