Matching preclusion for vertex-transitive networks

DOI10.1016/J.DAM.2016.02.001MaRDI QIDQ290107zbMATH OpenOpenAlexFDO

Authors Qiuli Li, Jinghua He, Heping Zhang

Publication date 1 June 2016

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5016662 (Why is no real title available?)
• scientific article; zbMATH DE number 1232919 (Why is no real title available?)
• 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
• Matching preclusion and conditional matching preclusion for regular interconnection networks
• Matching preclusion and conditional matching preclusion problems for tori and related Cartesian products
• Matching preclusion and conditional matching preclusion problems for twisted cubes
• Matching preclusion for \(k\)-ary \(n\)-cubes
• Matching preclusion for balanced hypercubes
• Matching preclusion for some interconnection networks
• Matching preclusion for the (n, k)-bubble-sort graphs
• Matching theory
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• On Representatives of Subsets
• Optimally super-edge-connected transitive graphs
• The (conditional) matching preclusion for burnt pancake graphs
• The Factorization of Linear Graphs

Cited in

(20)

• Fractional matching preclusion for \((n,k)\)-star graphs
• 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)
• The fractional (strong) matching preclusion number of complete \(k\)-partite graph
• Matching preclusion for some interconnection networks
• 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
• 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
• 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
• A short note of strong matching preclusion for a class of arrangement graphs
• Matching preclusion number in product graphs
• scientific article; zbMATH DE number 5919743 (Why is no real title available?)

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)