Matching preclusion for vertex-transitive networks

DOI10.1016/J.DAM.2016.02.001zbMATH Open1337.05094arXiv1502.01442OpenAlexW1626629448MaRDI QIDQ290107FDOQ290107

Authors: Qiuli Li, Jinghua He, Heping Zhang 

Publication date: 1 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: In interconnection networks, matching preclusion is a measure of robustness when there is a link failure. Let $G$ be a graph of even order. The matching preclusion number $mp(G)$ is defined as the minimum number of edges whose deletion results in a subgraph without perfect matchings. Many interconnection networks are super matched, that is, their optimal matching preclusion sets are precisely those induced by a single vertex. In this paper, we obtain general results of vertex-transitive graphs including many known networks. A $k$-regular connected vertex-transitive graph has matching preclusion number $k$ and is super matched except for six classes of graphs. From this many previous results can be directly obtained and matching preclusion for some other networks, such as folded $k$-cubes, Hamming graphs and halved $k$-cubes, are derived.

Full work available at URL: https://arxiv.org/abs/1502.01442

Recommendations

• Matching preclusion and conditional matching preclusion for regular interconnection networks
• Generalized Matching Preclusion in Bipartite Graphs
• Matching preclusion for some interconnection networks
• Matching preclusion and conditional matching preclusion for bipartite interconnection networks. II: Cayley graphs generated by transposition trees and hyper-stars
• Matchings in vertex-transitive bipartite graphs
• Matching preclusion and conditional matching preclusion for bipartite interconnection networks. I: Sufficient conditions
• Matching preclusion for \(n\)-dimensional torus networks
• Matching preclusion for \(n\)-grid graphs
• Matching preclusion number of graphs
• Strong matching preclusion for \(k\)-composition networks

zbMATH Keywords

networksvertex-transitive graphsmatching preclusion

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cites Work

• Matching theory
• The Factorization of Linear Graphs
• Title not available (Why is that?)
• On Representatives of Subsets
• Matching preclusion for balanced hypercubes
• Title not available (Why is that?)
• Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products
• Matching preclusion for some interconnection networks
• Matching preclusion for \(k\)-ary \(n\)-cubes
• Optimally super-edge-connected transitive graphs
• The (conditional) matching preclusion for burnt pancake graphs
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• Matching preclusion and conditional matching preclusion for bipartite interconnection networks. I: Sufficient conditions
• Matching preclusion and conditional matching preclusion for bipartite interconnection networks. II: Cayley graphs generated by transposition trees and hyper-stars
• Title not available (Why is that?)
• Matching preclusion for the (n, k)-bubble-sort graphs
• Matching preclusion and conditional matching preclusion for regular interconnection networks

Cited In (20)

• Fractional matching preclusion number of graphs and the perfect matching polytope
• Conditional matching preclusion for hypercube-like interconnection networks
• Conditional fractional matching preclusion for burnt pancake graphs and pancake-like graphs (extended abstract)
• Matching preclusion for some interconnection networks
• The fractional (strong) matching preclusion number of complete \(k\)-partite graph
• Conditional matching preclusion for regular bipartite graphs and their Cartesian product
• Fractional matching preclusion for arrangement graphs
• A note on generalized matching preclusion in bipartite graphs
• Matching preclusion for direct product of regular graphs
• A Short Note of Strong Matching Preclusion for a Class of Arrangement Graphs
• Conditional fractional matching preclusion of \(n\)-dimensional torus networks
• Strong matching preclusion for \(k\)-composition networks
• Matching preclusion for \(n\)-grid graphs
• The fractional matching preclusion number of complete \(n\)-balanced \(k\)-partite graphs
• Fractional Matching Preclusion for (n,k)-Star Graphs
• Matching preclusion for \(n\)-dimensional torus networks
• Fractional matching preclusion numbers of Cartesian product graphs
• Matching preclusion and conditional matching preclusion for bipartite interconnection networks. I: Sufficient conditions
• Matching preclusion number in product graphs
• Title not available (Why is that?)

This page was built for publication: Matching preclusion for vertex-transitive networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290107)