Matching preclusion number of graphs
Copyright policy )Matching preclusion number of graphs
The \emph{matching preclusion number} of a graph $G$, denoted by $\mpo(G)$, 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.
23 pages
- Zhejiang Gongshang University Hangzhou College of Commerce China (People's Republic of)
- China Jiliang University China (People's Republic of)
- University of Rochester United States
- School of Computer Science Switzerland
- Oakland University United States
Network design and communication in computer systems, perfect matching, matching preclusion number, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Graph theory (including graph drawing) in computer science, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), extremal problem, Nordhaus-Gaddum problem, interconnection networks
Network design and communication in computer systems, perfect matching, matching preclusion number, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Graph theory (including graph drawing) in computer science, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), extremal problem, Nordhaus-Gaddum problem, interconnection networks
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).15 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!