MM-alternating Hamilton paths and MM-alternating Hamilton cycles

We study MM-alternating Hamilton paths, and MM-alternating Hamilton cycles in a simple connected graph GG on νν vertices with a perfect matching MM. Let GG be a bipartite graph, we prove that if for any two vertices xx and yy in different parts of GG, d(x)+d(y)≥ν/2+2d(x)+d(y)≥ν/2+2, then GG has an MM-alternating Hamilton cycle. For general graphs, a condition for the existence of an MM-alternating Hamilton path starting and ending with edges in MM is put forward. Then we prove that if κ(G)≥ν/2κ(G)≥ν/2, where κ(G)κ(G) denotes the connectivity of GG, then GG has an MM-alternating Hamilton cycle or belongs to one class of exceptional graphs. Lou and Yu [D. Lou, Q. Yu, Connectivity of kk-extendable graphs with large kk, Discrete Appl. Math. 136 (2004) 55–61] have proved that every kk-extendable graph HH with k≥ν/4k≥ν/4 is bipartite or satisfies κ(H)≥2kκ(H)≥2k. Combining our result with theirs we obtain we prove the existence of MM-alternating Hamilton cycles in HH.