Article ID Journal Published Year Pages File Type
419587 Discrete Applied Mathematics 2010 10 Pages PDF
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
, , ,