Paper Info
Title
Matching Preclusion Number in Cartesian Product of Graphs and its Application to Interconnection Networks.
Abstract
The matching preclusion number of a graph G, mp(G), is the minimum number of edges whose deletion leaves a resulting graph that has neither perfect matchings nor almost perfect matchings. Besides its theoretical linkage with conditional connectivity and extremal graph theory, the matching preclusion number is a measure of robustness in interconnection networks. In this paper we develop general properties related to matchings in the Cartesian product of graphs which allow us, in a simple manner, to establish the matching preclusion number for some interconnection (product) networks, namely: hyper Petersen, folded Petersen, folded Petersen cube, hyperstar, star-cube and hypercube. We also conclude that the Cartesian product of graphs operation inherits the matching preclusion number optimality from factor graphs of even order, which reinforces the Cartesian product as a good network-synthesizing operator.
Year
Venue
Keywords
2013
ARS COMBINATORIA
Cartesian Product,Perfect Matching,Matching Preclusion,Interconnection Network,Fault Tolerance
Field
DocType
Volume
Factor graph,Discrete mathematics,Combinatorics,Cartesian product,Cartesian product of graphs,Matching preclusion,Operator (computer programming),Extremal graph theory,Hypercube,Mathematics,Cube
Journal
112
ISSN
Citations 
PageRank 
0381-7032
2
0.38
References 
Authors
8
3
Name
Order
Citations
PageRank
Aline Ribeiro de Almeida161.58
Fábio Protti235746.14
Lilian Markenzon3326.88