判断k-可序哈密顿-连通图的新条件

摘要

A graph G on n vertices（n≥3） is k-ordered Hamiltonian-connected for an integer k,2≤k≤n,if for every ordered set S={v1,v2,…,vk} of k distinct vertices in G,there exists a Hamiltonian path from v1 to vk that contains the vertices of S in the designated order.In this paper,It proved that for a graph G on n vertices with d（u）＋d（v）≥n＋1 for any two nonadjacent vertices u,v of G.If G is「k＋1/2」-connected k-ordered graph,let 2≤k≤n/12 be an integer.Then G is k-ordered Hamiltonian-connected.%具有n个顶点的图G（n≥3）是k-可序哈密顿-连通的（k是整数,且2≤k≤n）,如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了：对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d（u）＋d（v）≥n＋1.如果G是「k＋1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.