Distributing vertices along a Hamiltonian cycle in Dirac graphs |
| |
Authors: | Gábor N Sárközy Stanley Selkow |
| |
Institution: | a Computer Science Department, Worcester Polytechnic Institute, Worcester, MA 01609, USA b Computer and Automation Research Institute, Hungarian Academy of Sciences, P.O. Box 63, Budapest H-1518, Hungary |
| |
Abstract: | A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance is defined as the number of edges in a shortest path of G joining u and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are ω,n0>0 such that if G is a Dirac graph on n≥n0 vertices, d is an arbitrary integer with 3≤d≤ωn/2 and S is an arbitrary subset of the vertices of G with 2≤|S|=k≤ωn/d, then for every sequence di of integers with 3≤di≤d,1≤i≤k−1, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, a1,a2,…,ak, such that the vertices of S are visited in this order on C and we have |
| |
Keywords: | Graph theory Hamiltonian cycle |
本文献已被 ScienceDirect 等数据库收录! |
|