Complete Forcing Numbers of Polyphenyl Systems

Document Type : Research Paper

Authors

1 School of Mathematical Sciences, Xinjiang Normal University, Urumqi, Xinjiang 830054, P. R. China

2 Department of Mathematics, Xinjiang Normal University, Urumqi, Xinjiang 830054, P.R.China

3 College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, P.R.China

Abstract

The idea of “forcing” has long been used in many research fields, such as colorings, orientations, geodetics and dominating sets in graph theory, as well as Latin squares, block designs and Steiner systems in combinatorics (see [1] and the references therein). Recently, the forcing on perfect matchings has been attracting more researchers attention. A forcing set of M is a subset of M contained in no other perfect matchings of G. A global forcing set of G, introduced by Vukiˇcevi´c et al., is a subset of E(G) on which there are distinct restrictions of any two different perfect matchings of G. Combining the above “forcing” and “global” ideas, Xu et al. [5] introduce and define a complete forcing set of G as a subset of E(G) on which the restriction of any perfect matching M of G is a forcing set of M. The minimum cardinality of complete forcing sets is the complete forcing number of G. In this paper, we give the explicit expressions for the complete forcing number of several classes of polyphenyl systems.

Keywords

Main Subjects

Files

Share

How to cite

Statistics