Results 181 to 190 of about 292 (214)

Matching preclusion number in product graphs

Theoretical Computer Science, 2019
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Eddie Cheng, Yaping Mao
exaly   +2 more sources

Fractional Strong Matching Preclusion for DHcube

Parallel Processing Letters, 2021
Let [Formula: see text] be a set edges and [Formula: see text] be a set of edges and/or vertices of a graph [Formula: see text], then [Formula: see text] (resp. [Formula: see text]) is a fractional matching preclusion set (resp. fractional strong matching preclusion set) if [Formula: see text] (resp. [Formula: see text]) contains no fractional perfect
He Zhang, Jinyu Zou, Shuangshuang Zhang, Chengfu Ye   +3 more
openaire   +2 more sources

MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR CROSSED CUBES

Parallel Processing Letters, 2012
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
Eddie Cheng 0001, Sachin Padmanabhan
openaire   +2 more sources

MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR AUGMENTED CUBES

Journal of Interconnection Networks, 2010
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 incident to a single vertex.
Eddie Cheng 0001, Randy Jia, David Lu
openaire   +1 more source

Matching Preclusion for the Shuffle-Cubes

Parallel Processing Letters, 2018
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. A graph is maximally matched if its matching preclusion number is equal to its minimum degree, and is super matched if the matching preclusion number can only be achieved by ...
Sai Antantapantula, Christopher Melekian, Eddie Cheng 0001   +2 more
openaire   +1 more source

Matching preclusion and conditional matching preclusion for pancake and burnt pancake graphs

International Journal of Parallel, Emergent and Distributed Systems, 2013
The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion destroys all perfect matchings in the graph. The optimal matching preclusion sets are often precisely those which are induced by a single vertex of minimum degree.
Eddie Cheng 0001, Philip Hu, Roger Jia, László Lipták, Brian Scholten, James R. Voss   +5 more
openaire   +1 more source

Matching Preclusion for Exchanged Hypercubes

Journal of Interconnection Networks, 2019
As spanning subgraphs of hypercubes, exchanged hypercubes contain less edges but maintain lots of desired properties of hypercubes. This paper considers matching preclusion, a kind of measures of edge-fault tolerance, of exchanged hypercubes EH(s, t). We show that EH(s, t) is maximally matched, that is, for s ≥ t, mp(EH(s, t)) = t + 1 and EH(s, t) is ...
Qiuli Li, Wantao Ning
openaire   +1 more source

Fractional matching preclusion of graphs

Journal of Combinatorial Optimization, 2016
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Yan Liu, Weiwei Liu
openaire   +2 more sources

Conditional matching preclusion sets

Information Sciences, 2009
The matching preclusion concept was introduced as a measure of robustness in interconnection networks. A desired property is that the only minimum way to preclude a perfect (respectively, almost-perfect) matching is to delete all edges incident to a single vertex (respectively, all edges incident to two vertices).
Eddie Cheng 0001, Linda M. Lesniak, Marc J. Lipman, László Lipták   +3 more
openaire   +1 more source

Conditional Matching Preclusion for Folded Hypercubes

Journal of Interconnection Networks, 2019
Let G be a graph with an even number of vertices. The matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching, and the conditional matching preclusion number of G is the minimum number of edges whose deletion results in a graph with no isolated vertices and without a perfect ...
Ruizhi Lin, Heping Zhang
openaire   +1 more source