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 K1,3. The k-th power of G, denoted by Gu, 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 G3 have the same cardinality, then G3 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-flee graph, then G3 is generalized induced matching extendable.

General Induced Matching Extendability of $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.