Integer k-matching preclusion of graphs

MaRDI QIDQ6438947zbMATH OpenFDO

Authors Caibing Chang, Yan Liu

Publication date 1 June 2023

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)

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.

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)