Conditional matching preclusion for the arrangement graphs

Eddie Cheng, Marc J. Lipman, László Lipták, David Sherman

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

The matching preclusion number of a graph is the minimum number of edges whose deletion resultsinagraph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those inducedby asingle 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.

Original languageEnglish (US)
Pages (from-to)6279-6289
Number of pages11
JournalTheoretical Computer Science
Volume412
Issue number45
DOIs
StatePublished - Oct 21 2011

Bibliographical note

Funding Information:
The research was partially supported by the NSF-REU under Grant DMS 0649099.

Keywords

  • Arrangement graphs
  • Interconnection networks
  • Perfect matching

Fingerprint Dive into the research topics of 'Conditional matching preclusion for the arrangement graphs'. Together they form a unique fingerprint.

Cite this