Cycles through a prescribed vertex set in N-connected graphs

摘要

A well-known result of Dirac (Math. Nachr. 22 (1960) 61) says that given n vertices in an n-connected G, G has a cycle through all of them. In this paper, we generalize Dirac's result as follows: Given at most 3/2n vertices in an n-connected graph G when ngreater than or equal to3 and V(G)greater than or equal to3/2n, then G has a cycle through exactly n vertices of them. This improves the previous known bound given by Kaneko and Saito (J. Graph Theory 15(6) (1991) 655). (C) 2003 Elsevier Inc. All rights reserved. [References: 18]