The square of a path (cycle) is the graph obtained by joining every pair of vertices of distance two in the path (cycle). Let G be a graph on n vertices with minimum degree delta(G). Posa conjectured that if delta(G)greater than or equal to 2/3n, then G contains the square of a hamiltonian cycle. This is also a special case-of a conjecture of Seymour. In this paper, we prove that for any epsilon > 0, there exists a number m, depending only on a, such that if delta(G)greater than or equal to(2/3 + epsilon) n + m, then G contains the square of a hamitonian path between any two edges, which implies the squares of a hamiltonian cycle. (C) 1995 Academic Press, Inc. [References: 5]
展开▼
