General Induced Matching Extendability of $G^3$

Abstract:

      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.