Title

Conditional Matching Preclusion for the Alternating Group Graphs and Split-Stars

Document Type

Article

Publication Date

4-2011

Publication Source

International Journal of Computer Mathematics

Volume

88

Issue

6

Inclusive pages

1120 - 1136

Publisher

Taylor & Francis

Peer Reviewed

yes

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 article we find this number and classify all optimal sets for the alternating group graphs, one of the most popular interconnection networks, and their companion graphs, the split-stars. Moreover, some general results on the conditional matching problem are presented.

Keywords

interconnection networks, perfect matching, alternating group graphs, split-stars

Disciplines

Computer Sciences | Discrete Mathematics and Combinatorics | Mathematics | OS and Networks

This document is currently not available here.

  Contact Author

Share

COinS