Matching preclusion number of graphs
From MaRDI portal
Abstract: The emph{matching preclusion number} of a graph , denoted by , is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we first give some sharp upper and lower bounds of matching preclusion number. Next, graphs with large and small matching preclusion number are characterized, respectively. In the end, we investigate some extremal problems and the Nordhaus-Gaddum-type relations on matching preclusion number.
Recommendations
- Conditional matching preclusion number of graphs
- Fractional matching preclusion number of graphs
- Strong matching preclusion number of graphs
- Matching preclusion number in product graphs
- Matching preclusion for n-grid graphs
- Fractional matching preclusion number of graphs and the perfect matching polytope
- Fractional matching preclusion of graphs
- Note on matching preclusion number of random graphs
- Matching preclusion of the generalized Petersen graph
- Fractional matching preclusion numbers of Cartesian product graphs
Cites work
- A survey of Nordhaus-Gaddum type relations
- Conditional matching preclusion for hypercube-like interconnection networks
- Graph theory
- Graph theory and interconnection networks.
- scientific article; zbMATH DE number 3141016 (Why is no real title available?)
- scientific article; zbMATH DE number 5016662 (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 the folded Petersen cube
- Matching preclusion and conditional matching preclusion problems for twisted cubes
- Matching preclusion for \(k\)-ary \(n\)-cubes
- MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS
- Matching preclusion for some interconnection networks
- Matching preclusion for the (n, k)-bubble-sort graphs
- On the NP-completeness of the perfect matching free subgraph problem
- Strong matching preclusion
- Strong matching preclusion for \(k\)-ary \(n\)-cubes
- Strong matching preclusion number of graphs
- Strong matching preclusion under the conditional fault model
- The Factorization of Linear Graphs
Cited in
(23)- Graphs with restricted valency and matching number
- Strong matching preclusion number of graphs
- Matching preclusion number in product graphs
- Matching preclusion for n-grid graphs
- Conditional matching preclusion for regular bipartite graphs and their Cartesian product
- Fractional matching preclusion number of graphs
- Matching numbers in fuzzy graphs
- Fractional matching preclusion of product networks
- Matching preclusion for direct product of regular graphs
- Matching preclusion for vertex-transitive networks
- scientific article; zbMATH DE number 5016662 (Why is no real title available?)
- A note on the matching preclusion number of Caylay graphs on abelian groups with given degree
- Matching preclusion of the generalized Petersen graph
- Matching preclusion of boxdot products
- On anti-Kekulé and s-restricted matching preclusion problems
- Erdös-Gallai-type problems for distance-edge-monitoring numbers
- Strong matching preclusion
- Monitoring the edges of product networks using distances
- Integer k-matching preclusion of graphs
- Strong matching preclusion for folded hypercubes
- Higher order matching preclusion for regular interconnection networks
- Conditional fractional matching preclusion number of graphs
- Note on matching preclusion number of random graphs
This page was built for publication: Matching preclusion number of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1711840)
