Anzeige
Erschienen in:
01.05.2015
Complete forcing numbers of catacondensed hexagonal systems
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2015
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let G be a graph with edge set E(G) that admits a perfect matching M. 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čević 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, we 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\). First we establish some initial results about these two novel concepts, including a criterion for a complete forcing set, and comparisons between the complete forcing number and global forcing number. Then we give an explicit formula for the complete forcing number of a hexagonal chain. Finally a recurrence relation for the complete forcing number of a catacondensed hexagonal system is derived.