经过指定边的Hamilton圈

Hamiltonian Cycle Through Specified Edges

本文证明,如果对图G 的每一对不相邻的顶点u 和v 有dG(u)+dG(v)≥v+n,那么G 中任意n 条独立边包含在G 的一个Hamilton 圈中;设n 和k 为正整数,且满足:n≤k-1.如果G 是k-连通图并且G 的独立数α满足:α≤k-n,那么,任意n 条独立边包含在G 的一个Hamilton 圈中.

It is proved that if for each pair of nonadjacent vertices u and v of G,do(u)+dG(v)≥(?)+n,then any n independent edges of G lie on a Hamiltonian cycle.Let n and k be positive integers such that n≤k-1.We prove that if G is ak-connected graph,and if the independence number α of G satisfies α≤k-n,thenany n independent edges lie on a Hamiltonian cycle of G.