Conditional matching preclusion for the arrangement graphs

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

doi:10.1016/j.tcs.2011.07.007

Conditional matching preclusion for the arrangement graphs

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

Research output: Contribution to journal › Article › peer-review

27 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 language	English (US)
Pages (from-to)	6279-6289
Number of pages	11
Journal	Theoretical Computer Science
Volume	412
Issue number	45
DOIs	https://doi.org/10.1016/j.tcs.2011.07.007
State	Published - Oct 21 2011
Externally published	Yes

Bibliographical note

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

Keywords

Arrangement graphs
Interconnection networks
Perfect matching

Publisher link

10.1016/j.tcs.2011.07.007

Find It

Find It at U of M Libraries

Cite this

@article{fb51a0a22d294efb8ec96dfc18cb766c,

title = "Conditional matching preclusion for the arrangement graphs",

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.",

keywords = "Arrangement graphs, Interconnection networks, Perfect matching",

author = "Eddie Cheng and Lipman, \{Marc J.\} and L{\'a}szl{\'o} Lipt{\'a}k and David Sherman",

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

year = "2011",

month = oct,

day = "21",

doi = "10.1016/j.tcs.2011.07.007",

language = "English (US)",

volume = "412",

pages = "6279--6289",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "45",

}

TY - JOUR

T1 - Conditional matching preclusion for the arrangement graphs

AU - Cheng, Eddie

AU - Lipman, Marc J.

AU - Lipták, László

AU - Sherman, David

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

PY - 2011/10/21

Y1 - 2011/10/21

N2 - 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.

AB - 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.

KW - Arrangement graphs

KW - Interconnection networks

KW - Perfect matching

UR - https://www.scopus.com/pages/publications/84862211533

UR - https://www.scopus.com/pages/publications/84862211533#tab=citedBy

U2 - 10.1016/j.tcs.2011.07.007

DO - 10.1016/j.tcs.2011.07.007

M3 - Article

AN - SCOPUS:84862211533

SN - 0304-3975

VL - 412

SP - 6279

EP - 6289

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 45

ER -

Conditional matching preclusion for the arrangement graphs

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this