A new sufficient condition for Hamiltonicity of graphs

被引：17

作者：

Li, R ^{[1
]}

机构：

[1] Univ S Carolina, Dept Math Sci, Aiken, SC 29801 USA

来源：

INFORMATION PROCESSING LETTERS | 2006年 / 98卷 / 04期

关键词：

combinatorial problems; graphs Hamiltonian cycles; Hamiltonian paths;

D O I：

10.1016/j.ipl.2006.01.003

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u) + d(v) + delta(u, v) >= n + 1 for each pair of distinct non-adjacent vertices it and v in G, where S(u, v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：159 / 161

页数：3