Matching preclusion for direct product of regular graphss
Matching preclusion for direct product of regular graphss
复制标题
正则图直积的匹配排除
DOI：
10.1016/j.dam.2019.08.016
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Zhao Weisheng
中科院分区：
文献类型：
--
作者：
Lin Ruizhi;Zhang Heping;Zhao Weisheng
设G是具有偶数个顶点的图。图G的匹配排除数，记为mp(G)，是边的最小数目，其删除使得所得到的图不存在完全匹配。如果mp(G)等于G的最小度，则G是最大匹配的；如果G的每个最优匹配排除集由关联到单个顶点的边组成，则G是超匹配的。本文主要研究图的直积的匹配排除。对于任意两个图G和H，我们用G×H表示它们的直积，并证明了mp(G×H)⩾mp(G)mp(H)，这意味着两个最大匹配图的直积也是最大匹配的。此外，对于任意两个至少有三个顶点的正则图，我们证明了如果它们中至少有一个是最大匹配的，那么它们的直积是超配的，因此它们的强积也是超配的。
Let G be a graph with an even number of vertices. The matching preclusion number of G, denoted by m p (G), is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching. G is maximally matched if m p (G) is equal to the minimum degree of G and is super matched if every optimal matching preclusion set of G consists of edges incident to a single vertex. In this paper, we focus on matching preclusion for direct product of graphs. For any two graphs G and H, we denote their direct product by G× H and show m p (G× H)⩾ m p (G) m p (H), which implies that the direct product of two maximally matched graphs is also maximally matched. Furthermore, for any two regular graphs with at least three vertices, we show that if at least one of them is maximally matched, then their direct product is super matched, and as a consequence, their strong product is also super matched.