M-alternating Hamilton paths and M-alternating Hamilton cycles

Abstract

We study $M$-alternating Hamilton paths and $M$-alternating Hamilton cycles in a simple connected graph $G$ on $\nu$ vertices with a perfect matching $M$. Let $G$ be a bipartite graph, we prove that if for any two vertices $x$ and $y$ in different parts of $G$, $d(x)+d(y)\ge \nu /2+2$, then $G$ has an $M$-alternating Hamilton cycle. For general graphs, a condition for the existence of an $M$-alternating Hamilton path starting and ending with edges in $M$ is put forward. Then we prove that if $\kappa (G)\ge \nu /2$, where $\kappa (G)$ denotes the connectivity of $G$, then $G$ has an $M$-alternating Hamilton cycle or belongs to one class of exceptional graphs. Lou and Yu \cite{LY} have proved that every $k$-extendable graph $H$ with $k\ge \nu /4$ is bipartite or satisfies $\kappa (H)\ge 2k$. Combining this result with those we obtain we prove the existence of $M$-alternating Hamilton cycles in $H$.

published in Discrete Mathematics