3阶幂图的广义导出匹配可扩性
General Induced Matching Extendability of \$G^3\$

DOI：10.3770/j.issn:1000-341X.2010.03.009

 作者 单位 吴龙树 中国计量学院数学系, 浙江 杭州 310018 闫运生 河南工业大学理学院, 河南 郑州 450052 王勤 中国计量学院数学系, 浙江 杭州 310018

图\$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.