3阶幂图的广义导出匹配可扩性

General Induced Matching Extendability of $G^3$

中文关键词:  几乎完美匹配  导出匹配可扩的  广义导出匹配可扩性  幂图.

英文关键词:near perfect matching  induced matching extendable  general induced matching extendability  power of graph.

中文摘要:

      图$G$称为是导出匹配可扩的,如果图$G$的每一个导出匹配都包含在它的一个完美匹配中.图$G$称为是广义导出匹配可扩的,如果图$G$的每一个导出匹配都包含在它的一个最大基数匹配中.图$G$称为是无爪的,如果它不包含任何与$K_{1,3}$同构的导出子图.图$G$的$k$阶幂图记为$G^k$,是指在它的顶点集$V(G)$中,两个顶点相邻当且仅当它们在图$G$中的距离至多为$k$.在本文中我们证明了,如果图$G$的最大匹配和$G^3$的最大匹配的基数相同,那么$G^3$是广义导出匹配可扩的.我们证明了这个结果是最佳可能的.同时,我们证明了如果$G$是连通的无爪图,那么$G^3$是广义导出匹配可扩的.

英文摘要:

      A graph $G$ is induced matching extendable if every induced matching of $G$ is included in a perfect matching of $G$. A graph $G$ is generalized induced matching extendable if every induced matching of $G$ is included in a maximum matching of $G$. A graph $G$ is claw-free, if $G$ dose not contain any induced subgraph isomorphic to $K_{1,3}$. The $k$-th power of $G$, denoted by $G^k$, is the graph with vertex set $V(G)$ in which two vertices are adjacent if and only if the distance between them is at most $k$ in $G$. In this paper we show that, if the maximum matchings of $G$ and $G^3$ have the same cardinality, then $G^3$ is generalized induced matching extendable. We also show that this result is best possible. As a result, we show that if $G$ is a connected claw-free graph, then $G^3$ is generalized induced matching extendable.