Propagation characteristics of elastic waves in 2D phononic crystal consisting of parallel cylinders embedded periodically in a homogeneous host medium are investigated. The multiple scattering method and the Bloch theorem are used to derive the dispersive equation. The dispersive curves and the band gaps between them are evaluated numerically in the reduced Brillouin zone. The graded interphase between the cylinders and the host are considered. The influences of the graded interphase with different gradient profiles are discussed based on the numerical results.