A characterization of graphs without long induced paths |
| |
Authors: | G bor Bacs ,Zsolt Tuza |
| |
Affiliation: | Gábor Bacsó,Zsolt Tuza |
| |
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. |
| |
Keywords: | |
|
|