Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419587 | Discrete Applied Mathematics | 2010 | 10 Pages |
Abstract
The forcing number or the degree of freedom of a perfect matching MM of a graph GG is the cardinality of the smallest subset of MM that is contained in no other perfect matchings of GG. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Heping Zhang, Dong Ye, Wai Chee Shiu,