Affordable Access

Publisher Website

Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Volume
160
Issue
12
Identifiers
DOI: 10.1016/j.dam.2012.03.014
Keywords
  • Cycles
  • Tori
  • Cartesian Product
  • Matching Preclusion
  • Conditional Matching Preclusion

Abstract

Abstract The matching preclusion number of an even graph is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. The conditional matching preclusion number of an even 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 and no perfect matchings. In this paper we study this problem for the tori by proving matching preclusion and conditional matching preclusion results of the Cartesian products of graphs involving cycles. Our results generalize the one given for k-ary n-cube by Wang et al. (2010) [10] as well as provide classification for optimal conditional matching preclusion sets for these graphs.

There are no comments yet on this publication. Be the first to share your thoughts.