THE SQUARE OF PATHS AND CYCLES

The square of a path (cycle) is the graph obtained by joining every pa ir of vertices of distance two in the path (cycle). Let G be a graph o n n vertices with minimum degree delta(G). Posa conjectured that if de lta(G)greater than or equal to 2/3n, then G contains the square of a h amiltonian cycle. This is also a special case-of a conjecture of Seymo ur. In this paper, we prove that for any epsilon > 0, there exists a n umber m, depending only on a, such that if delta(G)greater than or equ al 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 hamiltonia n cycle. (C) 1995 Academic Press, Inc.