M-Alternating Hamilton Paths and M-Alternating Hamilton Cycles

Yueping Li 1, Dingjun Lou 1, and Zanbo Zhang 1, 2
1 Department of Computer Science, Sun Yat-sen University, Guangzhou 510275, P. R. China

2 Department of Computer Engineering, Guangdong Industry Technical College, Guangzhou 510300, P. R. China

Abstract     Full Text  PPT

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$. When $G$ is bipartite, we prove that if $\kappa\geq\nu/4+1$, where $\kappa$ denotes the connectivity of $G$, then $G$ has an $M$-alternating Hamilton cycle. In 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 unless $G$ belongs to one exceptional class of graphs, there exists an $M$-alternating Hamilton cycle in $G$ with $\kappa\geq\nu/2$. Lou and Yu have proved that every $k$-extendable graph $H$ with $k\geq\nu/4$ is either bipartite or satisfies $\kappa\geq 2k$. Combining this result with those we obtain we prove the existence of $M$-alternating Hamilton cycles in $H$.