The matching number in powers of cycles

Question

What can be said about the matching number of powers of cycles, $C_n^k$, where $n$ be even?

I think powers of cycles do not have have perfect matching for $k\ge3$, for, these graphs have odd cycles. But, how could we determine the matching number, i.e., the maximum number of independent edges in the graph?Any hints? Thanks beforehand.

Answer 1

Whenever $G$ has a perfect matching, so does $G^k$ for all $k\ge 1$. This is because $G^k$ has all the edges $G$ does, plus possibly more, so the perfect matching in $G$ also works for $G^k$. Since $C_n$ has a perfect matching for even $n$, so does $C_n^k$.

Odd cycles do not imply the nonexistence of perfect matchings. For example, $K_4$ has both odd cycles and a perfect matching.

Answer 2

If you mean cartesian products, it is also easy. For a graph $G$ with $n$ vertices, $G \times G$ has a subgraph $S$ with $n$ components each isomorphic to $G$. Thus if $G$ has a perfect matching, as is the case for even cycle graphs, you can use that matching on each component of $S$, which also applies for $G \times G$. You do this inductively for any power of Cartesian products.