Anti-forcing spectra of perfect matchings of graphs |
| |
Authors: | Kai Deng Heping Zhang |
| |
Affiliation: | 1.School of Mathematics and Statistics,Lanzhou University,Lanzhou,People’s Republic of China;2.School of Mathematics and Information Science,Beifang University of Nationalities,Yinchuan,People’s Republic of China |
| |
Abstract: | Let M be a perfect matching of a graph G. The smallest number of edges whose removal to make M as the unique perfect matching in the resulting subgraph is called the anti-forcing number of M. The anti-forcing spectrum of G is the set of anti-forcing numbers of all perfect matchings in G, denoted by (hbox {Spec}_{af}(G)). In this paper, we show that any finite set of positive integers can be the anti-forcing spectrum of a graph. We present two classes of hexagonal systems whose anti-forcing spectra are integer intervals. Finally, we show that determining the anti-forcing number of a perfect matching of a bipartite graph with maximum degree four is a NP-complete problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|