首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A characterization of graphs without long induced paths
Authors:Gbor Bacs  Zsolt Tuza
Institution: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:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号