Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871210 | Discrete Applied Mathematics | 2018 | 13 Pages |
Abstract
A matching preclusion set of a graph is an edge set whose deletion results in a graph without perfect matchings or almost perfect matchings. The Cartesian product of n paths is called an n-grid graph. In this paper, we study the matching preclusion problems for n-grid graphs and obtain the following results. If an n-grid graph has an even order, then it has the matching preclusion number n, and every optimal matching preclusion set is trivial except for the case of P2mâ¡P3, the Cartesian product of a path on 2m vertices and a path on 3 vertices, when the nontrivial optimal matching preclusion sets are completely characterized. If the n-grid graph has an odd order, then it has the matching preclusion number n+1, and all the optimal matching preclusion sets are characterized.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Qi Ding, Heping Zhang, Hui Zhou,