Article ID Journal Published Year Pages File Type
419678 Discrete Applied Mathematics 2013 9 Pages PDF
Abstract

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, and the conditional matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph with no isolated vertices that has neither perfect matchings nor almost perfect matchings. In this paper, we find these two numbers for the burnt pancake graphs and show that every optimal (conditional) matching preclusion set is trivial.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,