On the diameter ofi-center in a graph without long induced paths
Jinquan Dong · Journal of Graph Theory · 1999
A graph G is said to be Pt-free if it does not contain an induced path on t vertices. The i-center Ci(G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, ⌊t/2⌋ ≤ i ≤ t − 2, with the property that, in every connected Pt-free graph G, the i-center Ci(G) of G induces a connected subgraph of G. In this article, the sharp upper bound on the diameter of G[Ci(G)] is established for every i ∈ I(t). The sharp lower bound on I(t) is obtained consequently. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 235–241, 1999