Some results on graphs without long induced paths

Let I(t) be the set of integers with the property that in every P_t-free connected graph G, the i-center C,(G) induces a connected subgraph. What is the minimum element of I(t)? In this paper, we prove that this minimum is 2t/3] − 1 if t ≡ 0 or 2(mod3) and is 2t/3] otherwise. Furthermore, as conjectured by G. Bacsó and Z. Tuza, the set I(t) is an interval. In addition, a counterexample to a conjecture proposed by G. Bacsó and Z. Tuza is also presented. © 1996 John Wiley & Sons, Inc.