A characterization of graphs without long induced paths
Gábor Bacsó, Źsolt Tuza · Journal of Graph Theory · 1990
Abstract In a connected graph define the k‐center as the set of vertices whose distance from any other vertex is at most k. We say that a vertex set S d‐dominates G if for every vertex x there is a y ∈ S whose distance from x is at most d. Call a graph Pt‐free if it does not contain a path on t vertices as an induced subgraph. We prove that a connected graph is P2k‐1‐free (P2k‐free) if and only if each of its connected induced subgraphs H satisfy the following property: The k‐center of H (k ‐ 1)‐dominates ((k ‐ 2)‐dominates) H. Moreover, we show that the subgraph induced by the (t ‐ 3)‐center in any Pt‐free connected graph is again connected and has diameter at most t ‐ 3.