M-alternating Hamilton paths and M-alternating Hamilton cycles

We study M -alternating Hamilton paths, and M -alternating Hamilton cycles in a simple connected graph G on ν 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 ) ≥ ν / 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 κ ( G ) ≥ ν / 2 , where κ ( 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 [D. Lou, Q. Yu, Connectivity of k -extendable graphs with large k , Discrete Appl. Math. 136 (2004) 55–61] have proved that every k -extendable graph H with k ≥ ν / 4 is bipartite or satisfies κ ( H ) ≥ 2 k . Combining our result with theirs we obtain we prove the existence of M -alternating Hamilton cycles in H .