Matching Preclusion and Conditional Matching Preclusion Problems for Twisted Cubes
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 the matching preclusion number and the conditional matching preclusion number for twisted cubes, an improved version of the well-known hypercube. Moreover, we also classify all the optimal matching preclusion sets.
Additional Information
© 2010 Utilitas Mathematica. Research partially completed at the Oakland University Summer Mathematics Institute.Attached Files
Published - Bhaskar2010p13604Congr._Numer.pdf
Files
Name | Size | Download all |
---|---|---|
md5:bc7a3c8ba7d40a65a2f167990a5336b5
|
4.1 MB | Preview Download |
Additional details
- Eprint ID
- 23511
- Resolver ID
- CaltechAUTHORS:20110502-082828795
- Oakland University Summer Mathematics Institute
- Created
-
2011-05-04Created from EPrint's datestamp field
- Updated
-
2020-03-09Created from EPrint's last_modified field