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 v 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) >= 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) >= 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 [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 >= nu/4 is bipartite or satisfies kappa(H) >= 2k. Combining our result with theirs we obtain we prove the existence of M-alternating Hamilton cycles in H.