Integer k-matching preclusion of graphs

arXiv2306.01216MaRDI QIDQ6438947FDOQ6438947

Authors: Caibing Chang, Yan Liu 

Publication date: 1 June 2023

Abstract: As a generalization of matching preclusion number of a graph, we provide the (strong) integer $k$-matching preclusion number, abbreviated as $M{P}^k$ number ($SM{P}^k$ number), which is the minimum number of edges (vertices and edges) whose deletion results in a graph that has neither perfect integer $k$-matching nor almost perfect integer $k$-matching. In this paper, we show that when $k$ is even, the ($SM{P}^k$) $M{P}^k$ number is equal to the (strong) fractional matching preclusion number. We obtain a necessary condition of graphs with an almost-perfect integer $k$-matching and a relational expression between the matching number and the integer $k$-matching number of bipartite graphs. Thus the $M{P}^k$ number and the $SM{P}^k$ number of complete graphs, bipartite graphs and arrangement graphs are obtained, respectively.

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Fractional graph theory, fuzzy graph theory (05C72) Graph theory (05C99)

This page was built for publication: Integer k-matching preclusion of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438947)