Strong matching preclusion |
| |
| Authors: | Jung-Heum Park |
| |
| Affiliation: | a School of Computer Science and Information Engineering, The Catholic University of Korea, Bucheon, Republic of Koreab Department of Computer Science and Engineering, Sogang University, Seoul, Republic of Korea |
| |
| Abstract: | The matching preclusion problem, introduced by Brigham et al. R.C. Brigham, F. Harary, E.C. Violin, and J. Yellen, Perfect-matching preclusion, Congressus Numerantium 174 (2005) 185-192], studies how to effectively make a graph have neither perfect matchings nor almost perfect matchings by deleting as small a number of edges as possible. Extending this concept, we consider a more general matching preclusion problem, called the strong matching preclusion, in which deletion of vertices is additionally permitted. We establish the strong matching preclusion number and all possible minimum strong matching preclusion sets for various classes of graphs. |
| |
| Keywords: | Perfect and almost perfect matching Matching preclusion Vertex and/or edge deletion Restricted hypercube-like graph Recursive circulant |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
