Conditional matching preclusion for the arrangement graphs |
| |
Authors: | Eddie Cheng David Sherman |
| |
Affiliation: | a Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, United Statesb Department of Mathematics and Statistics, Indiana University—Purdue University Fort Wayne, Fort Wayne, IN 46805, United Statesc University of Michigan, Ann Arbor, MI 48109, United States |
| |
Abstract: | The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper we find this number and classify all optimal sets for the arrangement graphs, one of the most popular interconnection networks. |
| |
Keywords: | Interconnection networks Perfect matching Arrangement graphs |
本文献已被 ScienceDirect 等数据库收录! |
|